\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode,enumerate}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 1},%
pdfsubject={University of Waterloo, CS 240, Winter 2026},%
pdfauthor={MP}]{hyperref}
%\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}

\newcommand{\alg}[1]{\ensuremath\mbox{\it #1}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\newcounter{algorithmeligne}
\newcommand{\instr}[1]{%\underline
                        {\bf #1}}
\newcommand{\nomproc}[1]{{\rm\bf #1}}
\newenvironment{algorithme}
        {
        \setcounter{algorithmeligne}{0}

        \newcommand{\lign}{
                \stepcounter{algorithmeligne}
                {\footnotesize \arabic{algorithmeligne}.}\>
                }
        \begin{center}
        \begin{tabular}{|c|}
        \hline
        \begin{minipage}{1cm}
        \small
        \,
        \ \ \\[-11mm]
        \begin{tabbing}
\hskip1cm\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\\\kill
        }
        {
        \end{tabbing}
        \ \ \\[-8mm]
        \end{minipage}
        \\\hline
        \end{tabular}
        \end{center}
        }


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Winter 2026}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
{\bf Olga Veksler, Mark Petrick}\\
\vspace{3mm}
{\bf Copyright $\copyright$ 2026 Distribution (except by the authors) is prohibited.}\\ 
\textbf{Due Date: Tuesday, January 20 at 5:00pm}
\end{center}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode

\noindent Please read
\url{https://student.cs.uwaterloo.ca/~cs240/w26/assignments.phtml#guidelines} for guidelines on submission.  
\textbf{Each question must be submitted individually to Crowdmark.} 
Submit early and often.\\
~\\
\textbf{Grace period:} submissions made before 7:59PM on January 20 will be accepted without penalty. Your last submission will be graded. Please note that submissions made after 7:59PM {\bf will not be graded} and may only be reviewed for feedback. \\  
~\\
\textbf{Reminder:} all logarithms are in base 2 unless stated otherwise.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[1+1+1+1=4 marks]}

Find the mistake in each of the following proofs from the definition of the order notation. 

\begin{itemize}
\part{a} Let $f(n) =  50n\log{n} + 4 n$ and $g(n) = n \log{n} $. Show that $f(n)$ is $O(g(n)).$

Proof:  
For all $n \geq  1,$ we have that $50n\log{n} + 4n  \leq 50n\log{n} + 4n \log{n} = 54 n 
\log{n}$. So take $n_0 = 1$ and $c = 54.$

\part{b} 
Let $f(n) =  50n^2 + 4 n$ and $g(n) = n^3 $. Show that $f(n)$ is $O(g(n)).$

Proof: 
For all $n \geq 0,$ we have that $50n ^2 + 4n  \leq 50n^3 + 4n^3 = 54 n^3$. So take $n_0 = 0$ and $c = 54.$


\part{c} 

Let $f(n) =  2n^2 + 4 n$ and $g(n) = n^2 $. Show that $f(n)$ is $\Theta(g(n)).$

Proof: 
For all $n \geq 10,$ we have that $2n^2 + 4 n \leq 2n^2 + 4 n^2= 6 n^2$. So take $n_0 = 10$ and $c = 6.$


\part{d} 

Let $f(n) =  2n^2 - 4 n$ and $g(n) =  n^2 $. Show that $f(n)$ is $\Omega(g(n)).$

Proof: For all $n \geq 1$ we have that $2n^2 - 4 n \geq 2n^2$. So take $n_0 = 1$ and $c = 2.$







\end{itemize}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3+3+3+3=12 marks]}

Provide a complete proof of the following statements from first principles (i.e., using the original definitions of order notation).

\begin{itemize}
\part{a} $2^{2^n} \log{n} +2^{2^{100}}\cdot 2^n \in O(2^{2^n} \log{n})$
\part{b} $0.5n^4 - 10 n^{3.99}  - 15n\in \Omega(n^4)$
\part{c} $n^{5}+2^{100}n^{2} +2^{100}\in o(n^{5}\log{n})$
\part{d} $ n^2 +n\in \omega(n^{1.9999})$
\end{itemize}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3+3=6 marks]}

Prove or disprove each of the following statements. 
All functions map from $\mathbb{N} \to \mathbb{R}^+$.

\begin{itemize}


\part{a}  $\frac{f(n)g(n)+ \log{g(n)}}{f(n)+2g(n)} $ is $\Theta(\min\{f(n),g(n)\})$.

\part{b}  $(\log n)^{\log n} \in O(n^2)$.

\end{itemize}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3 marks]}

Arrange the following functions by the order of their growth rates:   
$$4^n, 2^{\cos{n}}, 3^n, 2^{n\log{n}}, (\log{n})^{100}, n^2, \frac{n^2+n^{10}}{\log{n}}, 
(n^3+\log{n})^{(n^2 - n^4-10)}$$ This question will be marked as an `all or nothing' question. No justification is required.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[5 marks]}
Define a function $f \colon \mathbb{N} \to \mathbb{R}^+$  such that $f$
satisfies these three conditions:
\begin{enumerate}[(1)]
\item $f(n) \in O(n^4)$
\item $f(n) \not\in\Theta(n^4)$
\item $f(n) \not\in o(n^4)$
\end{enumerate}
Justify your answer.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4+4=8 marks]}


Analyze the following pieces of pseudocode and give a tight ($\Theta$)
bound on the running time as a function of $n$. Show your work. In
all cases, $n$ is assumed to be a positive integer.
\begin{enumerate}



\part{a}



\begin{verbatim}
x = 0
for i = 1 to n do
    for j = i to n do
        if i == j then
            k = n
            while k > 0 do
                x = x + 1
                k = k/3
\end{verbatim}

\part{b}
\begin{verbatim}
sum = 0
for i = 1 to n
     sum = sum + i
     j = i
     while j > 0
        sum = sum + j
        j = j - 1
        k = j
        while k <  j - i
            sum = sum + 1
            k = k + 1

      
\end{verbatim}

\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[4 marks]}

Analyze the best  case time efficiency of the following algorithm.
$A$ is an array of size $n$ storing integers in the range from $1$ to  $n$. Furthermore,  if integer $i$ occurs in array $A$, then it occurs at most $\sqrt{n}$ times. You can assume $\sqrt{n}$ is an integer.


\begin{verbatim}

Algorithm Lazy(A,n)  

i = 0
sum = 0
while i < n
   sum = sum + A[i]
   sum2 = 0
   while sum2 < sum  
      sum2 = sum2 + 1
   i = i + 1
      

\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3 marks]}

In the sum below, replace `*' with the correct expression to derive the lower bound of ${\big ( \frac{n}{3} \big )}^2 c$ for the sum.  You can assume $n/3$ is an integer. Explain your work.

$$\sum_{i=1} ^n  \sum_{j=1}^i c \geq \sum_{i=*} ^*  \sum_{j=*}^* c = {\big ( \frac{n}{3} \big )}^2 c$$



\end{document}



    