\documentclass{article}
\usepackage[T1,T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{natbib}
\usepackage{listings}
\usepackage{datetime}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{wrapfig}
\usepackage{amsfonts}
\usepackage{tikz,tkz-graph,tkz-berge}
\usepackage[margin=2cm]{geometry}
\usepackage{xcolor}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,
    breaklines=true,
    captionpos=b,
    keepspaces=true,
    numbers=left,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=2
}

\lstset{style=mystyle}

\title{Домашнее задание 1 по курсу "Основные алгоритмы"}
\author{Иванов Максим\\группа Б05-901}
\newdate{date}{7}{2}{2020}
\date{\displaydate{date}}

\begin{document}

\maketitle
\newpage

\paragraph{1.a.} Используя определение, $f(n)=O(g(n))\Leftrightarrow \exists C>0, \exists N\in\mathbb{N}:
 \forall n\geqslant N\quad |f(n)|\leqslant C|g(n)|$.
 Взяв $C=1, N=\lceil a \rceil$, где $a$ --- основание логарфима, получим $n\leqslant n\log n$,
 для $\forall n\geqslant N$, так как $\log n \geqslant 1, \forall n\geqslant N$. Значит ответ: да.


\paragraph{1.б.} Допустим $\exists\varepsilon>0: n\log n=\Omega(n^{1+\varepsilon})$.
Тогда $\exists C>0, \exists N\in\mathbb{N}: \forall n\geqslant N\quad Cn^{1+\varepsilon}\leqslant n\log n$.
То есть $C\leqslant n^{-\varepsilon}\log n=\dfrac{\log n}{n^{\varepsilon}}, \forall n\geqslant N$.
По правилу Лопиталя $\displaystyle{\lim_{n\to\infty}}\dfrac{\log n}{n^{\varepsilon}}=
\displaystyle{\lim_{n\to\infty}}\dfrac{1/n}{\varepsilon n^{\varepsilon-1}}=
\displaystyle{\lim_{n\to\infty}}\dfrac{1}{\varepsilon n^{\varepsilon}}=0$. Это противоречит исходному
утверждению, ответ: нет.


\paragraph{2.1.а.} Исходные условие можно записать в виде: $f(n)\leqslant C_1 n^2,\quad g(n)\geqslant C_2,\quad g(n)\leqslant C_3 n$
(для любых $n$ больших соответсвтующих им $N_1, N_2, N_3$ из определений).
Возьмем $f(n)=n^2,\quad g(n)=\dfrac{n}{\log n}$. Понятно, что обе функции подходят, для $f$ все очевидно, для $g$ можно записать
$\dfrac{n}{\log n}\leqslant \dfrac{n}{\log 2}=Cn, \forall n\geqslant 2$ и так как $n$ растет быстрее $\log n$,
то $\dfrac{n}{\log n}\geqslant 1, \forall n\geqslant 2$. Тогда $h(n)=n\log n=\Theta(n\log n)$. Ответ: возможно.


\paragraph{2.1.б.} Если $h(n)=\Theta(n^3)$, то $\exists C>0, \exists N\in\mathbb{N}: \forall n\geqslant N\quad h(n)\geqslant Cn^3\Rightarrow
h(n)g(n)=f(n)\geqslant C'n^3, \forall n\geqslant N$ --- противоречие с $f(n)\leqslant C_2n^2$. Ответ: нет.


\paragraph{2.2} Верхняя оценка $O(n^2)$, при $f(n)=n^2, g(n)=1$. Нижняя оценка не существует, так как функция $h$ может быть сколь угодно малой,
например, $f(n)=\varepsilon, g(n)=1\Rightarrow h(n)=\varepsilon$.


\paragraph{3.}
Вначале заметим, $\displaystyle{\sum_{i=1}^{n}}\sqrt{i^3+2i+5}\leqslant\displaystyle{\sum_{i=1}^{n}}\sqrt{9n^3}=3n^{2.5}$.

Далее $\displaystyle{\sum_{i=1}^{n}}\sqrt{i^3+2i+5}\geqslant\displaystyle{\sum_{i=n/2}^{n}}\sqrt{i^3+2i+5}
\geqslant\displaystyle{\sum_{i=n/2}^{n}}\sqrt{i^3}\geqslant\displaystyle{\sum_{i=n/2}^{n}}\sqrt{(n/2)^3}=\dfrac{n^{2.5}}{2^{2.5}}$.

Значит, $\displaystyle{\sum_{i=1}^{n}}\sqrt{i^3+2i+5}=\Theta(n^{2.5})$.

\paragraph{4.} По условию, $f(n)<(3+\varepsilon)^n+Cn^{100}, \forall n>\max\{N_1, N_2\}$, где $N_1, N_2$ --
номера, начиная с которых, выполняются условия из определений $o(1)$ и $\Theta(n^{100})$ соответственно.
Так как полином растет много медленнее степени можем записать, что $f(n)=\Theta(3^n)$,
откуда после логарифмирования получаем, что $\log f(n)=\Theta(n)$ (тот факт, что можно прологарифмировать функцию внутри $\Theta$ сразу следует из определния, нужно взять логарифм от обеих частей неравенства).

\paragraph{5.} В первом цикле число действий $\left\lceil\dfrac{i}{2}\right\rceil$.
Во втором цикле число действий $\left\lfloor\log n\right\rfloor$.

Тогда в третьем ровно $\displaystyle{\sum_{i=0}^{b-1}}\left(\left\lceil\dfrac{i}{2}\right\rceil+
\left\lfloor\log n\right\rfloor\right)=b\cdot\left\lfloor\log n\right\rfloor+C\dfrac{b(b-1)}{4}=
\Theta(b)\Theta(\log n)+\Theta(b^2)$ действий.

В четвертом цикле $\displaystyle{\sum_{b=1}^{\lceil\sqrt{n}\rceil-1}}
\left(\Theta(b)\Theta(\log n)+\Theta(b^2)\right)=\Theta(n\log n)+\Theta(n^{3/2})=\Theta(n^{3/2})$
\lstinputlisting[language=C]{code.c}




\end{document}