\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 2025}\\
\vspace{2mm}
{\Large\bf Assignment 1}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, May 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
Read
\url{https://student.cs.uwaterloo.ca/~cs240/s25/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 20 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.



\begin{enumerate}

%%%%%%%% Q1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item {[3+3+4+4]} Provide a complete proof of the following statements from first
principles (i.e., using the original definitions of order notation).

\begin{enumerate}
\item $12 n^3 -11n^2+10 \in O(n^3)$

\item $12 n^3 -11n^2+10 \in \Omega(n^3)$

\item $n \log(\log(n)) \in o(n (\log(\log(n)))^2)$

\item $n^{n} \in \omega(n^{n/2})$
\end{enumerate}

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

\item {[10 marks]} 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}

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

\item {[6 marks]} 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}

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

\item 
Analyze the following pseudocode and give a tight ($\Theta$) bound on the running time
as a function of $n$. You can assume that all individual instructions
(including logarithm) are elementary, i.e. take constant time. Show your work.

\begin{enumerate}

\item {[3 marks]}
\begin{verbatim}
s = 0  
for i = 1 to n * n * n do
   for j = 1 to i * i  do
      s = s + 1
\end{verbatim}


\item {[3 marks]}
\begin{verbatim}
l = 0
for i = n + 1 to n^2 do 
   for j = 1 to ceiling(log(i)) do
       l = l + 1
   od  
od
\end{verbatim}



\item {[8 marks]}
\begin{verbatim}
m = 1
l = 0
s = 0
while m <= n do 
   for j = n - m to n do
      l = l + 1
   od 
   for j = 1 to ceiling(log n) do
      s = s + 1
   od 
   m = 3 * m
od
\end{verbatim}
\end{enumerate}

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

\item {[2+6 marks]}

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{enumerate}




\end{document}