\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, Spring 2025},%
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 Spring 2026}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, May 26 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 Read
\url{https://student.cs.uwaterloo.ca/~cs240/s26/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 19:59PM on May 26 will be accepted without penalty. Your last submission will be graded. Please note that submissions made after 19:59PM {\bf will not be graded} and may only be reviewed for feedback. \\  
~\\
\textbf{Reminder:} all logarithms are in base 2 unless stated otherwise.

%%%%%%%% Q1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{[3+3+3+4+4 marks]}

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

\begin{enumerate}
\part{a} $5n^3+n^2+10n+7 \in O(n^3)$
\part{b} $n^2(\log n)^{0.00001} \in \Omega(n^2)$
\part{c} $\frac{n^2}{n+\log n} \in \Theta(n)$
\part{d} $n \log(\log(n)) \in o(n (\log(\log(n)))^2)$
\part{e} $2^{n} \in \omega(n^{1/n})$
\end{enumerate}



%%%%%%%% Q2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[3+3+3+3 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. A
formal proof is not required, but you should justify your answer (in
all cases, $n$ is assumed to be a positive integer).
\begin{enumerate}
\part{a} 
\begin{verbatim}
  x = 0
  for i = 1 to n + 12 do
      x = x * 4
     for j = 389 to 20100 
        for k = 2i to 3i
            x = x * 77
\end{verbatim}
\part{b} 
\begin{verbatim}
   x = 0
   for i = 1 to ceiling(log(n))
      for j = 1 to i 
         for k = 1 to 10
             x = x + 1
\end{verbatim}
\part{c} 
\begin{verbatim}
   s = 0;
   for i = 1 to n*n do
      for j = 1 to i*i do
          s = s + 1;
\end{verbatim}
\part{d} 
\begin{verbatim}
   s = n
   while (s > 0)
     if (s is even)
        s = floor(s / 4)
     else
        s = 2 * s
\end{verbatim}
\end{enumerate}


%%%%%% Q3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{[2+2+2 marks]}

You are a TA for CS240 during W27. It is a cold snowy morning in Waterloo. You wake up late, spend 30 minutes shoveling snow, and barely make it to your office hours on time. Unfortunately, you did not even get a chance to buy coffee. You sit down tired, frozen, and questioning all of your life choices.

~\\ A few minutes later, a cheerful student named Leo walks in holding a large cup of coffee and asks for help proving that the recurrence
\[
T(n)=T(n-1)+1, \qquad T(1)=1
\]
has linear runtime.\\
Leo says he is trying to prove
\[
T(n)\leq cn
\]
for some constant \(c\), using induction.

~\\ He explains his proof:

Assume
\[
T(n)\leq cn.
\]

We show that
\[
T(n+1)\leq c(n+1).
\]

Since
\[
T(n+1)=T(n)+1,
\]

using the induction hypothesis,
\[
T(n+1)\leq cn+1.
\]
Leo then writes
\[
cn+1\leq cn+n=(c+1)n.
\]

Therefore,
\[
T(n+1)\leq (c+1)n.
\]
Leo smiles confidently, takes a sip of coffee, and says:
\begin{quote}
``This is still linear, so the proof should work!''
\end{quote}
As the TA, you are not convinced.

\begin{enumerate}
    \part{a} Assume Leo continues using the same style of argument repeatedly. Determine what upper bound he would get for
    \[
    T(n+2), T(n+3),\ldots, T(2n).
    \]

    \part{b} Explain why this shows that allowing the constant to increase at each induction step can eventually lead to a non-linear bound here. Explain why this is not a valid way to prove a linear upper bound in general.

    \part{c} Tell Leo what a correct induction proof would look like here.
\end{enumerate}

Your answer should clearly explain why the inductive step must end with the same constant \(c\) as the induction hypothesis.

\vspace{0.5em}

Strangely, by the end of the conversation, Leo's excitement about the problem and the fun of thinking carefully about the proof have worked better than coffee. For a moment, the snowy morning no longer feels so terrible, and you remember that you are actually happy with most of your life choices, including studying computer science at UWaterloo.

\newpage

\noindent {\bf The following exercises are provided for additional practice and are not part of the graded portion of the assignment. While these questions will not be 
evaluated, we strongly encourage you, and expect you, to work through 
them to deepen your understanding of the material. You are welcome to 
upload your solutions to Crowdmark for your own record-keeping and 
organization; however, no grades or feedback will be provided for these 
submissions. You may also ask questions about these exercises during 
office hours or on Piazza.}

%%%%%%%% Q4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{} For each of the following pairs of functions $f(n)$
and $g(n)$, determine the ``most appropriate'' symbol in the set $\{
o, \omega, \Theta, O, \Omega \}$ to complete the statement that
$f(n) \in \ \ \ \ (g(n))$ (if one of the symbols applies at all).
``Most appropriate'' means that you should not answer ``O'' if you
could answer ``o'' or ``$\Theta$''. Justify your answers even in the
cases when none of symbols applies at all.

\begin{enumerate}
\item $f(n) = 2025n^3+12871n^2+19$, $g(n)=\frac{2}{2025}n^4+2n$;

\item $f(n) = \log^2(n^4)$, $g(n)=\sqrt{n}$;

\item $f(n) = 16^{\log n^3}+n^5, \ \ g(n) = \frac{1}{2} n^{12} +100 n^6$;

\item $f(n) = n^2$, $g(n) = (\lceil {\frac{n}{2}}\rceil - \frac{n}{2}) n^2$;
\end{enumerate}

%%%%%%%% Q5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{} Prove or disprove each of the following
statements (give a counter example to disprove).

\begin{enumerate}
\item If $\log (f(n)) \in \Omega(\log(g(n)))$
then $f(n) \in \Omega(g(n))$.

\item If $f(n) \in O(h(n))$ and $g(n) \in O(h(n))$ then $\dfrac{f(n)}{g(n)} \in O(1)$.

\item If $f(n) \in o(g(n))$ then $\log(f(n)) \in o(\log(g(n))$.
\end{enumerate}






%%%%%%%% Q6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{} 

We consider two algorithms, Algo1 and Algo2, that solve the same
problem.  For any input of size $n$, Algo1 takes time $T_1(n)$ and
Algo2 takes time $T_2(n)$.  Prove or disprove each of the following
statements. To prove a statement, you should provide a formal proof
that is based on the definitions of the order notations.  To disprove
a statement, provide a counter example and explain it.
\begin{enumerate}
\item Suppose that $T_1(n) \in O(n^2(\log n)^{5})$ and $T_2(n) \in O(n^3(\log n)^{2})$. Does
  it imply that there exists $n_0$ such that for $n \ge n_0$, Algo1
  runs faster than Algo2 on inputs of size $n$?
\item Same question, assuming that $T_1(n) \in \Theta(n^2)$ 
  and $T_2(n) \in  \Theta(n^3)$.
\end{enumerate}


\end{document}