% Разбор задач практики 07.09.15

\Section{Разбор задач практики}
\vspace*{-1em}
\begin{MyList}
  \setlength{\itemsep}{0.5em}
  \item {\bf Простые задачи на асимптотику.}\\
    Найдите запись через $\Theta$.
    Если не существует, объяснить, почему, и записать через $\O$.
    \begin{InnerMyList}[4pt]
      \item $2n = \Theta(n)$, по определению =)
      \item $f(n) = 2n+1$,\\
        $\forall n \in \N \quad n \le 2n + 1 \le 2n + n \le 3n \SO f(n) = \Theta(n)$.
      \item $f(n) = n^2 + 5n + 1$,\\
        $\forall n \in \N \quad n^2 \le f(n) \le n^2 + 5n^2 + n^2 = 7n^2 \SO f(n) = \Theta(n^2)$.

        Способ \NO{2}: $5n + 1 = \O(n^2) \SO 5n + 1 = \alpha n^2 \SO f(n) \le (1 + \alpha)n^2 \SO f(n) = \Theta(n^2)$.
      \item $f(n) = \dfrac{n^2+3}{7n+1}$,\\
        Поделим числитель на знаменатель:
        $f(n) = (\tfrac{1}{7}n - \tfrac{1}{49}) + \underbrace{\dfrac{3 - \tfrac{1}{49}}{7n + 1}}_\text{беск. малая}
        \SO f(n) = \Theta(n)$.

        Способ \NO{2}: $\dfrac{n^2}{7n+n} \le f(n) \le \dfrac{n^2+n^2}{7n} \SO \tfrac{1}{8}n \le f(n) \le \tfrac{2}{7}n$.

      \item $f(n) = n(2 + \sin n)$,\\
        $-1 \le \sin n \le 1 \SO 1 \le 2 + \sin n \le 3 \SO n \le f(n) \le 3n \SO f(n) = \O(n)$.

      \item $f(n) = \frac{\arctg n}{n} + \frac{\log \log n}{\log n}$,\\
        Пусть $g(n) = \dfrac{\log \log n}{\log n}$.\\
        $\arctan n < \tfrac{\pi}{2} < \log \log n,\ n > \log n \SO f(n) \le 2g(n) = \Theta(g(n))$.

      \item Докажите: $\forall f, g > 0 \colon f + g = \Theta(\max(f, g))$,\\
        $\forall n \in \N \quad \max(f(n), g(n)) \le f(n) + g(n) \le 2 \max(f(n), g(n))$.
    \end{InnerMyList}

  \item {\bf Истина или ложь?}\\
    Проверьте корректность, докажите.
    \begin{InnerMyList}[4pt]
      \item $2^{n+3} = \Theta(2^n)$,\\
        Верно: $2^{n+3} = 8\cdot 2^n = \Theta(2^n)$.

      \item $2^{2n+1} = \Theta(2^n)$,\\
        Неверно, что $2^{2n+1} = \O(2^n)$, докажем от противного.\\
        Предположим, что
        $\forall n \ge N \quad 2^{2n+1} \le c \cdot 2^n \SO 2^{n + 1} \le c \SO n \le \log c - 1$. Противоречие.

      \item $g(n) = \O(f(n)) \SO 2^{g(n)} = \O(2^{f(n)})$,\\
        Неверно, возьмём $f(n) = 2n + 1,\ g(n) = n$. Получим условие предыдущей задачи.

      \item $g(n) = o(f(n)) \SO 2^{g(n)} = o(2^{f(n)})$,\\
        Верно, если $f(n) \xrightarrow[n \to \infty]{} +\infty$.

        $g(n) = o(f(n)) \EQ \tfrac{g(n)}{f(n)}\xrightarrow[n \to \infty]{} 0$.
        
        $\dfrac{2^{g(n)}}{2^{f(n)}} = 2^{g(n) - f(n)}$, но
        $f(n) - g(n) = f(n) - f(n) \cdot \tfrac{g(n)}{f(n)} = f(n)\left(1 - \tfrac{g(n)}{f(n)}\right) \ge 0.5f(n)$.

        $2^{g(n) - f(n)} \le \dfrac{1}{2^{0.5f(n)}} \xrightarrow[n \to \infty]{} 0$.

        \vspace{5mm}
        \underline{Способ \NO{2}:}
        $2^{g(n)} < c\cdot 2^{f(n)} \EQ g(n) < \log c + f(n)\ (*)$,
        но $\forall c_1 > 0 \quad g(n) < c_1 \cdot f(n)$, значит\\
        $(*) \Leftarrow c_1 \cdot f(n) < \log c + f(n) \EQ (1 - c_1)f(n) > -\log c
        \stackrel{c_1 < 1}{\iff} f(n) > \dfrac{-\log c}{1 - c_1}$.

        Возьмём $c_1 = \tfrac{1}{2}$, тогда $\exists N \quad \forall n \ge N \quad f(n) > -2\log c \SO 2^{g(n)} < c\cdot 2^{f(n)}$.

        Таким образом, $\forall c > 0 \quad \exists N \quad \forall n \ge N \quad 2^{g(n)} < c\cdot 2^{f(n)}$.

      \item $g(n) = \O(f(n)) \SO \log{g(n)} = \O(\log{f(n)})$,\\
      Верно, если $f(n) \xrightarrow[n \to \infty]{} +\infty$.

      $\log{g(n)} < c \cdot \log{f(n)} \EQ g(n) < \left( f(n) \right)^c$.

      $g(n) = \O(f(n)) \EQ \exists c_1 > 0 \quad g(n) < c_1 f(n)$, таким образом

      $g(n) < (f(n))^c \Leftarrow c_1 f(n) < (f(n))^c \EQ (f(n))^{c-1} > c_1$~--- верно, если $f(n) \to +\infty$ и $c > 1$.

      \item $g(n) = o(f(n)) \SO \log{g(n)} = o(\log{f(n)})$,\\
      Неверно, при $f(n) \to +\infty$.

      $\log{g(n)} < c\log{f(n)} \EQ g(n) < (f(n))^c$.

      $g(n) = o(f(n)) \EQ \forall c_1 > 0 \quad g(n) < c_1 f(n)$, таким образом

      $g(n) < (f(n))^c \Leftarrow c_1 f(n) < (f(n))^c \EQ (f(n))^{c-1} > c_1 \EQ (c - 1) \log f(n) > \log c_1$.

      Это неверно, если $f(n) \to +\infty$ и $c < 1$, так как\\
      $\log f(n)$ не может быть ограничен сверху числом $\dfrac{\log c_1}{c - 1}$.

      \item $f(n) + g(n) = \Theta(\frac{f(n) + g(n)}{2})$, верно по определению.

      \item $n^2 = \O(2^n)$,\\
        Верно, так как $\dfrac{n^2}{2^n} \xrightarrow[n \to \infty]{} 0 \SO n^2 = o(2^n) \SO n^2 = \O(2^n)$.

      \item $\log n = o(\mfrac{n}{\log n})$,\\
      Верно: $\log n = o(\mfrac{n}{\log n}) \EQ \log n < c \cdot \dfrac{n}{\log n} \EQ \log^2 n = n \EQ \log^2 n = o(n)$.

      Сделаем замену переменной $n = 2^y$, получим $y^2 = o(2^y)$, верное по предыдущему пункту.

      \item $\mfrac{n}{\log n} = \Theta(0.5 \cdot n)$,\\
      Неверно: $\mfrac{n}{\log n} = \Theta(0.5 \cdot n) \EQ n = \Theta(n\log n) \SO n\log n = \O(n)$.

      Если $n\log n < c \cdot n$, то $\log n < c$, что неверно, в силу неограниченности $\log n$.
    \end{InnerMyList}

  \item {\bf Реккурентность}
    \begin{InnerMyList}[4pt]
      \item $T(n) = 2T(\mfrac{n}{2}) + 1$,\\
      $2^k = n \EQ k = \log n$

      $T(n) = 2T(\mfrac{n}{2}) + 1 = 2(2T(\mfrac{n}{4}) + 1) + 1 =
      \underbrace{2(2(2(\dots(2}_\text{k двоек}T(\mfrac{n}{2^k}) + \underbrace{1) \dots) + 1) + 1) + 1}_\text{k единиц}$.

      Раскроем скобки:
      $2^k + 2^{k - 1} + \dots + 2^1 + 1 = 2^{k+1} - 1 = 2n - 1 = \Theta(n)$.

      Способ \NO{2} (по теореме):
      $a = 2, b = 2, c = 0, f(n) = 1 = \Theta(n^c), c < \log_ba \SO T(n) = \Theta(n)$.

      \item $T(n) = 3T(\mfrac{n}{2}) + n^2$,\\
      $2^k = n \EQ k = \log n$

      $T(n) = 3T(\mfrac{n}{2}) + n^2 = 3(3T(\mfrac{n}{2^2}) + (\mfrac{n}{2^1})^2) + (\mfrac{n}{2^0})^2 = \\
      = \underbrace{3(3(3(\dots(3}_\text{k троек}T(\mfrac{n}{2^k}) + \underbrace{(\mfrac{n}{2^{k-1}})^2) \dots) +
      (\mfrac{n}{2^2})^2) + (\mfrac{n}{2^1})^2) + (\mfrac{n}{2^0})^2}_\text{k штук} = \\
      = 3^k + 3^{k-1}(\mfrac{n}{2^{k-1}})^2 + 3^{k-2}(\mfrac{n}{2^{k-2}})^2 + \dots + 3(\mfrac{n}{2^1})^2 + 1\cdot (\mfrac{n}{2^0})^2 = \\
      = n^2((\mfrac{3}{4})^k + (\mfrac{3}{4})^{k-1} + (\mfrac{3}{4})^{k-2} + \dots + \mfrac{3}{4} + 1)
      \le n^2\sum\limits_{k=0}^{\infty}{(\mfrac{3}{4})^k} = n^2 \dfrac{1}{1 - \mfrac{3}{4}} = 4n^2 \SO \\
      n^2 \le T(n) \le 4n^2 \SO T(n) = \Theta(n^2)$.

      Способ \NO{2} (по теореме):\\
      $a = 3, b = 2, c = 2, f(n) = \Omega(n^2), c > \log_ba, 3(\mfrac{n}{2})^2 \le \mfrac{3}{8}n^2 \SO
      T(n) = \Theta(n^2)$.

      \item $T(n) = 5T(\mfrac{n}{2}) + n$,\\
      $2^k = n \EQ k = \log n$

      $T(n) = 5T(\mfrac{n}{2}) + n = 5(5T(\mfrac{n}{2^2}) + \mfrac{n}{2^1}) + \mfrac{n}{2^0} = \\
      = \underbrace{5(5(5(\dots(5}_\text{k штук}T(\mfrac{n}{2^k}) + \underbrace{\mfrac{n}{2^{k-1}}) \dots) +
      \mfrac{n}{2^2}) + \mfrac{n}{2^1}) + \mfrac{n}{2^0}}_\text{k штук} = \\
      = 5^k + 5^{k-1}\mfrac{n}{2^{k-1}} + 5^{k-2}\mfrac{n}{2^{k-2}} + \dots + 5\mfrac{n}{2^1} + 1\cdot \mfrac{n}{2^0} = \\
      = n((\mfrac{5}{2})^k + (\mfrac{5}{2})^{k-1} + (\mfrac{5}{2})^{k-2} + \dots + \mfrac{5}{2} + 1)
      = n\sum\limits_{i=0}^{k}{2.5^i} = n \dfrac{2.5^{k+1} - 1}{2.5 - 1} = \Theta(n \cdot 2.5^k)$.

      $2.5^k = 2.5^{\log n} = 2^{\log(2.5^{\log n})} = 2^{\log n \cdot \log 2.5} = n^{\log 2.5} \SO \\
      T(n) = \Theta(n^{1 + \log 2.5}) = \Theta(n^{\log 2 + \log 2.5}) = \Theta(n^{\log 5})$.

      Способ \NO{2} (по теореме):\\
      $a = 5, b = 2, c = 1, f(n) = \O(n^1), c < \log_ba \SO
      T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 5})$.
 
      \item $T(n) = 2T(\mfrac{n}{2}) + n\log n$,\\
      $a = 2, b = 2, f(n) = \Theta(n^1 \log^1 n), c = \log_ba = 1 \SO T(n) = \Theta(n^c \log^{1+1} n) = \Theta(n\log^2 n)$.

      \item $T(n) = 3T(\mfrac{n}{3}) + n$,\\
      $a = 3, b = 3, f(n) = \Theta(n^1 \log^0 n), c = \log_ba = 1 \SO T(n) = \Theta(n \log^{0+1} n) = \Theta(n\log n)$.

      \item $T(n) = T(n{-}1) + T(n{-}1) + 1$,\\
      $T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 2(2\dots (2T(1) + 1) + \dots + 1) + 1 =\\
      = 2^{n-1} + \dots + 2^1 + 1 = 2^{n} - 1 = \Theta(2^n)$.

      Можно доказать это и по индукции, посмотрев на первые несколько членов.

    \end{InnerMyList}
\end{MyList}
