\documentclass[dvipsnames]{article}
\usepackage[english]{babel}
\usepackage{multirow}
\usepackage[letterpaper,top=2cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{minted}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{fancyhdr}

\begin{document}
\section*{Week 1. Problem set (solutions by Matvey Panchenko)}

\thispagestyle{fancy}
\lhead{Matvey Panchenko (\texttt{m.panchenko@innopolis.university}), group B24-DSAI-03}

\begin{enumerate}
  \item
    Compute asymptotic worst case time complexity of the following algorithm (see pseudocode conventions in \cite[\S 2.1]{Cormen2022}).
    You \textbf{must} use $\Theta$-notation.
    For justification, provide execution cost and frequency count for each line in the body of the \texttt{secret} procedure.
    Optionally, you may provide the details for the computation of the running time $T(n)$ for worst case scenario.
    Proof for the asymptotic bound is not required for this exercise.

    \begin{minipage}{0.55\textwidth}
      \begin{minted}[linenos,escapeinside=||]{sql}
/* A is a 0-indexed array,
  * n is the number of items in A */
|\color{blue}secret|(A, n):
  |\color{red}for| i = 1 to n
    s := 1
    j := i - 1
    |\color{red}while| j < n |\color{teal}and| A[j] |$\geq$| A[i-1]
      j := j + s
      s := s + 2
    |\color{teal}exchange| A[i-1] |\color{teal}with| A[min(j, n - 1)]
      \end{minted}
    \end{minipage}%
    \begin{minipage}{0.4\textwidth}
      \small
      \begin{tabular}{ c | c | c }
      Line & Execution Cost & Frequency Count \\
      \hline
      1 & --- & --- \\
      2 & --- & --- \\
      3 & --- & --- \\
      4 &     c_4 &  n+1 \\
      5 &     c_5 &  n \\
      6 &     c_6 &  n \\
      7 &     c_7 &  $\sum_{i=1}^n t_i - 1$ \\
      8 &     c_8 &  $\sum_{i=1}^n t_i$ \\
      9 &     c_9 &  $\sum_{i=1}^n t_i$ \\
      10 &    c_{10} &  n \\
      \end{tabular}
    \end{minipage}

    \emph{(optional part) From this table, we conclude}
    \[
    T(n) = c_4(n+1) + c_5n + c_6n + c_7\frac{n(n+1)}{2} + c_8\frac{n(n+1)}{2} - c_8 + c_9\frac{n(n+1)}{2} - c_9 + c_{10}n = \Theta(n^2).
    \]
    qed.
\color{black}
  \item Indicate, for each pair of expressions (A, B) in the table below whether $A = O(B)$, $A = o(B)$, $A = \Omega(B)$, $A = \omega(B)$, or $A = \Theta(B)$. Write your answer in the form of the table with \emph{YES} or \emph{NO} written in each cell:

    \begin{center}
    \bgroup
    \def\arraystretch{1.5}
    \begin{tabular}{ |c|c||c|c|c|c|c| }
     \hline
     $A$ & $B$ & $A = O(B)$ & $A = o(B)$ & $A = \Omega(B)$ & $A = \omega(B)$ & $A = \Theta(B)$ \\
     \hline
     \hline
     $1 + \sin(n)$ & $\left(1 + \frac{1}{n}\right)^{\frac{1}{n}}$ & YES & NO & NO & NO & NO \\
     \hline
     $\sqrt[5]{n}$ & $\log_3^2 n$ & NO & NO & YES & YES & NO \\
     \hline
     $n^2$ & $\log_2^n n$ & YES & YES & NO & NO & NO \\
     \hline
     $(1 + \frac{1}{10^{100}})^n$ & $n^{(10^{100})}$ & YES & YES & NO & NO & NO \\
     \hline
     $\log_2 \left( (n + 1)! \right)$ & $n \log_2 n$ & YES & NO & YES & NO & YES \\
     \hline
    \end{tabular}
    \egroup
    \end{center}

  \clearpage
  \item Let $f$ and $g$ be functions from positive integers to positive reals.
    Assume $f(n) > n$ for $n > 2025$.
    Using the formal definition of asymptotic notation~\cite[\S 3.2]{Cormen2022}, prove \emph{formally} that
    \[
      \min(f(n) - \sqrt{n}, g(n) + n) = O(f(n) + g(n)).
    \]

    \begin{proof}
    By definition of big-$O$ notation, we need to show that there exist constants $c > 0$ and $n_0 > 0$ such that:
    \[
      \min(f(n) - \sqrt{n}, g(n) + n) \leq c(f(n) + g(n)),
    \]
    for all $n \geq n_0$.

    Let $n_0 = 2069$ and $c = 1$. Then for $n \geq n_0$, we have $f(n) > n$.

    By assumption:
    \[
    \min(f(n) - \sqrt{n}, g(n) + n) \leq c(f(n) + g(n)).
    \]

    Consider the following cases:

    \textbf{Case 1:} $\min = f(n) - \sqrt{n}$. \\
    In this case:
    \[
    f(n) - \sqrt{n} \leq f(n), \text{ since } \sqrt{n} \geq 0.
    \]
    Moreover:
    \[
    f(n) \leq f(n) + g(n).
    \]

    \textbf{Case 2:} $\min = g(n) + n$. \\
    In this case:
    \[
    g(n) + n \leq g(n) + f(n), \text{ by the condition that } f(n) > n.
    \]

    Thus, in both cases:
    \[
    \min(f(n) - \sqrt{n}, g(n) + n) \leq c(f(n) + g(n)).
    \]

    Therefore, we have shown that:
    \[
    \min(f(n) - \sqrt{n}, g(n) + n) = O(f(n) + g(n)).
    \]
    qed.
    \end{proof}
\end{enumerate}

\begin{thebibliography}{TheLongestRefName}

\bibitem[CLRS]{Cormen2022}
Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., 2022. \emph{Introduction to algorithms, Fourth Edition}. MIT press.

%\bibitem[Goldrich]{Goldrich2014}
%M. T. Goodrich, R. Tamassia, and M. H. Goldwasser. \emph{Data Structures and Algorithms in Java.} WILEY 2014.
\end{thebibliography}

\end{document}