% Copyright and Usage Information
% ===============================

% This file is provided solely for the personal and private use of students
% taking CSC110 at the University of Toronto St. George campus. All forms of
% distribution of this code, whether as given or with any changes, are
% expressly prohibited. For more information on copyright for CSC110 materials,
% please consult our Course Syllabus.

% This file is Copyright (c) 2021 Mario Badr and Tom Fairgrieve.
\documentclass{article}

\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}

\usepackage[margin=1in]{geometry}

\title{CSC110 Fall 2021: Term Test 2\\
       Question 2 (Analyzing Algorithm Running Time)}
\author{TODO: INSERT YOUR NAME HERE}
\date{Wednesday December 8, 2021}

% Some useful LaTeX commands. You are free to use these or not, and also add your own.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\C}{\texttt}

\begin{document}
\maketitle

\subsection*{Question 2, Part 1}

\noindent
We define the function $g: \N \to \R^{\geq 0}$ as $g(n) = 7n(n-1)^2$.
Consider the following statement:

\[
g(n) \in \cO(n^4)
\]

\begin{enumerate}

\item[(a)]
Rewrite the statement $g(n) \in \cO(n^4)$ by expanding the definition of Big-O.

\bigskip

\textbf{Solution}:

$\exists c, n_0 \in \R^+ \text{ s.t. } \forall n \in \N, n \ge n_0 \Rightarrow 7n(n-1)^2 \le c \cdot n^4$

\item[(b)]
Write the \emph{negation} of the statement from (a), using negation rules to simplify the statement as much as possible.

\bigskip

\textbf{Solution}:

$\forall c, n_0 \in \R^+, \exists n \in \N \text{ s.t. } n \ge n_0 \land 7n(n-1)^2 > c \cdot n^4$

\item[(c)]
Which of statements (a) and (b) is true? Provide a complete proof that justifies your choice.

In your proof, you may not use any properties or theorems about Big-O/Omega/Theta.  Work from the expanded statement from (a) or (b).

\bigskip

\textbf{Solution}:

I think statement (a) is true.

\begin{proof}
Want to show: $\exists c, n_0 \in \R^+ \text{ s.t. } \forall n \in \N, n \ge n_0 \Rightarrow 7n(n-1)^2 \le c \cdot n^4$ \\
Prove using Induction. \\
Take $c = 7, n_0 = 1$ \\
Let $n$ be an arbitrary natural number such that $n \ge (n_0 = 1)$ \\
What we want to prove becomes: $\forall n \in \N, n \ge 1 \Rightarrow 7n(n-1)^2 \le 7n^4$ \\
\\
Since $n \ge 1$, \\
Multiply both sides by $n^2$, we get $n^3 \ge n^2$ \\
From this, we also know that $(n - 1)^2 \le n^3$ \\
Also, since $n \ge 1$, \\
Multiply the inequality by $-2$, we get $-2n \le -2$ \\
Adding $1$ to both sides, we get $-2n + 1 \le -1$ \\
Putting the two inequalities together, we have $n^2 - 2n + 1 \le n^3 - 1 \le n^3$ \\ 
Factoring the polynomial on the left, we have $(n - 1)^2 \le n^3$ \\
Multiply both sides by $7n$, we get $7n(n - 1)^2 \le 7n^4$\\
Which is what we want to prove.

\end{proof}

\end{enumerate}

\subsection*{Question 2, Part 2}

\noindent
Consider the function below.

\begin{verbatim}
def f(nums: list[int]) -> list[int]:           # Line 1
    n = len(nums)                              # Line 2
    i = 1                                      # Line 3
    new_list = []                              # Line 4
    while i < n:                               # Line 5
        if nums[i] % 2 == 0:                   # Line 6
            list.append(new_list, i)           # Line 7
        else:                                  # Line 8
            new_list = [i * j for j in nums]   # Line 9
        i = i * 3                              # Line 10
    return new_list                            # Line 11
\end{verbatim}

\begin{enumerate}

\item[(a)]
Perform an \emph{upper bound analysis} on the worst-case running time of \texttt{f}.
The Big-O expression that you conclude should be \emph{tight}, meaning that the worst-case running time should be Theta of this expression, but you are not required to show that here.

\textbf{To simplify your analysis}, you may omit all floors and ceilings in your calculations (if applicable).
Use ``at most'' or $\leq$ to be explicit about where a step count expression is an upper bound.

\textbf{Solution}:

Let $n$ be the length of the input list \C{nums}

There is one loop in the function which loops through \C{nums} with $i$ increasing exponentially, which will run $\ceil{log_3(n)}$ times. Inside the loop, if then number is even, it takes $\cO(1)$ to append the item at the end of \C{new\_list}. If the number is odd, it sets \C{new\_list} to a list comprehension which iterates through all number in \C{nums}, performing an $\cO(1)$ multiplication every iteration, which takes exactly $n$ steps, which is a larger running time than if the number is even. Therefore, the inside of the loop will take at most $n$ steps, if all numbers \C{nums[i]} iterated are odd.

Since there are only constant-time operations outside the loop, the worst-case running time would be $\ceil{log_3(n)}$ iterations multiplied by at most $n$ steps per iteration, which is $n\ceil{log_3(n)}$ steps. 

Since $n\ceil{log_3(n)} \in \cO(n\ceil{log_3(n)})$, we can conclude that $WC_{f}(n) \in \cO(n\ceil{log_3(n)})$

\item[(b)]
Perform a \emph{lower bound analysis} on the worst-case running time of \texttt{f}.
The Omega expression you find should match your Big-O expression from part (a).

\textbf{Hint}: you don't need to try to find an ``exact maximum running-time'' input. \emph{Any} input family whose running time is Omega of (``at least'') the bound you found in part (a) will yield a correct analysis for this part.

\textbf{Solution}:

Let $n$ be the length of the input list \C{nums}, let \C{nums} be the list of length $n$ which every number is 1.

In this case, the if statement inside the loop always runs line 9 that takes $n$ steps, and then the $i = i * 3$ statement, which is 1 step, which is a total of $n + 1$ steps. The loop still iterates $\ceil{log_3(n)}$ times. Since there are only constant-time operations outside the loop, the total number of steps for this input is $(n + 1)\ceil{log_3(n)} + c$ which $c \in \N$ is a constant, which is $WC_{f}(n) \in \Omega(n\ceil{log_3(n)})$

\end{enumerate}

\begin{center}
    \textbf{SUBMIT THIS FILE AND THE GENERATED PDF q2.pdf FOR GRADING}
\end{center}
\end{document}
