%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Short Sectioned Assignment
% LaTeX Template
% Version 1.0 (5/5/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Frits Wenneker (http://www.howtotex.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[paper=a4, fontsize=11pt]{scrartcl}  % A4 paper and 11pt font size

\usepackage[colorlinks=true, allcolors=red]{hyperref}
\usepackage[T1]{fontenc}                           % Use 8-bit encoding that has 256 glyphs
%\usepackage{fourier}                              % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel}                        % English language/hyphenation
\usepackage{mathtools}                             % More complete math support in Latex than amsthm
\usepackage{amsmath,amsfonts,amsthm}               % Math packages
\usepackage{amssymb}                               % Additional math symbols.
\usepackage{graphicx}                              % Graphics with e.g. \includegraphics{file.png}.
%\usepackage{subfigures}                            % Have multiple figures in one.
\usepackage{caption}                               % Customize caption formatting.
\usepackage{subcaption}                            % Subfigures.
\usepackage{tabularx}                              % Width controlled tabulars.

\usepackage{sectsty}                               % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape}   % Make all sections centered, the default font and small caps

\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\usepackage{fancyhdr}                             % Custom headers and footers
\pagestyle{fancyplain}                            % Makes all pages in the document conform to the custom headers and footers
\fancyhead{}                                      % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{}                                   % Empty left footer
\fancyfoot[C]{}                                   % Empty center footer
\fancyfoot[R]{\thepage}                           % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt}                % Remove header underlines
\renewcommand{\footrulewidth}{0pt}                % Remove footer underlines
\setlength{\headheight}{13.6pt}                   % Customize the height of the header

\numberwithin{equation}{section}                  % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section}                    % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section}                     % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt}                         % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

%\usepackage{mathtools}
%\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
%\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}

\newcommand{\heads}{\textsc{h}}
\newcommand{\tails}{\textsc{t}}

\newcommand{\logten}{\log}                        %\mathrm{log}\hspace{0.05in}}
\newcommand{\logtwo}{\lg}                         %\mathrm{lg}\hspace{0.05in}}
\newcommand{\loge}{\ln}                           %\mathrm{ln}\hspace{0.05in}}

\theoremstyle{definition}
\newtheorem*{solution}{Solution}

\usepackage{algpseudocode, algorithm}

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{ECS60 \hfill Dept. of Computer Science, University of California, Davis} % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Homework \#1 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}


\author{Natalie Pueyo Svoboda, 997466498} % Put your name here

\date{\today}

\begin{document}

\maketitle

%Classmate collaborator(s): If you collaborated with fellow students, you \emph{must} list them here.

\section{First Problem}
    \begin{solution}
      To prove that $f(n)=\mathcal{O}(n^2)$, if $f(n)=3n^2+2n+4$, I have to prove that there are constants $c$ and $M$ such that $\forall n \geq M$, $f(n) \leq c \cdotp g(n)$, where $g(n)=n^2$.
      In other words, there is a constant, $c$ that when multiplied $g(n)$, will allow $g(n)$ to always overtake $f(n)$ $\forall n \geq M$.
      In this case, $f(n)=3n^2+2n+4 \leq c \cdotp n^2$.

      To make the proof easier, I chose $M=1$ such that $n \geq 1$.
      I can then use this definition to find a term greater than each term in $f(n)$ so that $f(n)=3n^2+2n+4 \leq c \cdotp n^2$.
      The resulting terms have to deal with the constants in $f(n)$.

      Because $n$ was defined such that $n \geq 1$, we can then multiply both sides by $n$ to show that $n^2 \geq n$ resulting in
      \begin{equation*}
        n^2 \geq n \geq 1
      \end{equation*}
      by multiplying each term in the inequality by the constant we want to remove, we can show that:
      \begin{equation*}
        2n^2 \geq 2n \geq 2
      \end{equation*}
      and
      \begin{equation*}
        4n^2 \geq 4n \geq 4
      \end{equation*}
      which takes care of the $2n$ and $4$ constants respectivelly.
      To find a value greater than $f(n)$'s first term, we use the definition of the $\geq$ operator: $3n^2 \geq 3n^2$ by definition.

      This leads to the following inequality:
      \begin{equation*}
        3n^2+2n+4 \leq 3n^2+2n^2+4n^2
      \end{equation*}
      Each term on the right is greater than or equal to its corresponding term on the left which makes the sum of all the right terms greater than $f(n)$.
      \begin{equation*}
        3n^2+2n+4 \leq 9n^2
      \end{equation*}

      This means that if $g(n)$ is multiplied by the constant $c=9$, after $n \leq M$, where $M=1$, $f(n) \leq c \cdotp g(n)$ proving that $f(n)=\mathcal{O}(n^2)$.
      % https://math.stackexchange.com/questions/437098/big-o-notation-prove-that-n2-2n-3-is-mathcal-on2
      % by AleksandrH
      % and use definition on hw page
    \end{solution}

\section{Second Problem}
    \begin{solution}
      If $f(n)=log(n)$ and $f(n)=\mathcal{O}(g(n))$ it can be proven that $g(n)=n$ if $lim_{n \rightarrow \infty} \frac{log(n)}{n} = c$ for some constant $c \geq 0$.
      Using L'Hopital's rule \[lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=\frac{f'(n)}{g'(n)}\] such that
      \begin{equation*}
        \begin{split}
          lim_{n \rightarrow \infty} \frac{log(n)}{n} & = lim_{n \rightarrow \infty} \frac{f'(n)}{g'(n)} = c\\
          & = lim_{n \rightarrow \infty} \frac{1}{n} \cdotp \frac{1}{1} = c\\
          & = lim_{n \rightarrow \infty} \frac{1}{n} = c\\
          & = 0 = c
       \end{split}
     \end{equation*}
     Which satisfies the condition that $c \geq 0$ proving that $log(n)=\mathcal{O}(n)$.
     This proof was done with the assumption that $log(n)$ was $ln(n)$.
     However, it is also true for other bases because the addition of a base just adds a constant which is ignored in Big-O notation.

     This can also be used to prove that $n^k log(n) = \mathcal{O}(n^{k+1})$ for any constant $k$.
     \begin{equation*}
       \begin{split}
         lim_{n \rightarrow \infty} \frac{n^k log(n)}{n^{k+1}} & = lim_{n \rightarrow \infty} \frac{f'(n)}{g'(n)} = c\\
         & = lim_{n \rightarrow \infty} \frac{n^{k-1} (k \cdotp log(n) + 1}{(k+1)n^k} = c\\
         & = lim_{n \rightarrow \infty} \frac{k \cdotp log(n) + 1}{n(k+1)} = c\\
         & = \frac{1}{k+1} lim_{n \rightarrow \infty} \frac{k \cdotp log(n) + 1}{n} = c\\
         & = lim_{n \rightarrow \infty} \frac{f'(n)}{g'(n)}\\
         & = \frac{1}{k+1} lim_{n \rightarrow \infty} \frac{k}{n} \cdotp \frac{1}{1} = c\\
         & = \frac{k}{k+1} lim_{n \rightarrow \infty} \frac{1}{n} = c\\
         & = \frac{k}{k+1} \cdotp 0 = 0 = c
      \end{split}
    \end{equation*}
    This also satisfies the condition that $c \geq 0$ proving that $n^k log(n) = \mathcal{O}(n^{k+1})$.
    For this second proof it was necessary to use L'Hopital's Rule a second time to make the proof possible.
    \end{solution}

\section{Third Problem}
    \begin{solution}
      The logarithmic identity to change the base of a logarithm is \[log_a x = \frac{log_b x}{log_b a}\]
      Using this identity we can prove that if we have two constants $a$ and $b$, and $f(n)=log_a n$, then $log_a n = \mathcal{O}(log_b n)$ and that $log_b n = \mathcal{O}(log_a n)$.
      By using the identity we can show that \[log_a n = \mathcal{O} \left(\frac{log_b n}{log_b a}\right)\] and since $log_b a$ is a constant it gets discarded from the Big-O notation.
      This results in \[log_a n = \mathcal{O}(log_b n)\]
      The same excercise can be done for $f(n)=log_b n$ where \[log_b n = \mathcal{O}\left(\frac{log_a n}{log_a b}\right)\] where again we discard the constant $log_a b$ resulting in \[log_b n = \mathcal{O}(log_a n)\]
    \end{solution}

\section{Fourth Problem}
    \begin{solution}
      If we imply that $f_i=\mathcal{O}(f_{i+1})$ for all $1 \leq i \leq 5$
      \begin{center}
        \begin{tabular}{l | l}
          $f(n)$ & $\mathcal{O}(g(n))$ \\ \hline
          $n^3+2n+1$ & $\mathcal{O}(n^3)$ \\
          $n log(n^2)$ & $\mathcal{O}(n \cdotp log(n^2))$ \\
          $n^2 log(n)$ & $\mathcal{O}(n^2 log(n))$ \\
          $2^n$ & $\mathcal{O}(2^n)$ \\
          $3^n$ & $\mathcal{O}(3^n)$ \\
          $1023n^2+2n+45$ & $\mathcal{O}(n^2)$ \\
        \end{tabular}
      \end{center}
      The $\mathcal{O}(g(n))$ of each given formula was plotted in R to determine which ones grew faster asymptotically.
      This would make it easy to rank them such that $f_i=\mathcal{O}(f_{i+1})$ for all $1 \leq i \leq 6$.
      Figure~\ref{fig:growth}.1 shows how all 6 equations act as $n$ grows larger.

      \begin{figure*}[ht]
        \centering
        \begin{subfigure}[t]{0.5\textwidth}
          \centering
          \includegraphics[height=2.5in]{big-o_graphs_closup.jpeg}
          \caption{$g(n)$ plots when $n=80$}
        \end{subfigure}%
      ~
        \begin{subfigure}[t]{0.5\textwidth}
          \centering
          \includegraphics[height=2.5in]{big-o_graphs.jpeg}
          \caption{$g(n)$ plots when $n=1000$}
        \end{subfigure}
      \caption{Plots of $\mathcal{O}(g(n))$ for the various $f(n)$ equations as $n$ grows larger}
      \end{figure*}
      \label{fig:growth}
      % I wonder if I have to justify it? Worry later
    \end{solution}
    With the plots the equations can be ranked according to the speed of their growth as:
    \[n \cdotp log(n^2), n^2, n^2 \cdotp log(n), n^3, 2^n, 3^n\]
    Making $f_1=n \cdotp log(n^2)$, $f_2=1023n^2+2n+45$, $f_3=n^2 \cdotp log(n)$, $f_4=n^3+2n+1$, $f_5=2^n$, and $f_6=3^n$.

\section{Fifth Problem}
    \begin{solution}
      To get the Big-O of a sum, one has to first find the resulting formula of the sum.
      The sum's for this problem is: $\sum_{i=0}^n i$ which expanded gives:
      \[S = \sum_{i=0}^n i = 1 + 2 + \ldots + (n-1) + n\]
      To solve for the formula,
      \begin{equation*}
        \begin{split}
          2 \cdotp S = 2 \cdotp \sum_{i=0}^n i & = (1 + 2 + \ldots + (n-1) + n) + (1 + 2 + \ldots + (n-1) + n)\\
          & = (1 + 2 + \ldots + (n-1) + n) + (n + (n-1) + \ldots + 2 + 1)\\
          & = [1+n] + [2+(n-1)] + ... + [(n-1) + 2] + [n + 1]\\
          & = n \cdotp (n+1)
        \end{split}
      \end{equation*}
      When solving for $S$, the result is $S = \sum_{i=0}^n i = \frac{n \cdotp (n+1)}{2}$.
      This can then be used to prove that $\sum_{i=0}^n i =\mathcal{O}(n^2)$ because the dominant term of $\frac{n \cdotp (n+1)}{2}$ is $n^2$ from simplifying $S$ to $\frac{1}{2}(n^2+n)$.
    \end{solution}

\section{Sixth Problem}
    \begin{solution}
      For any positive integer $n$ and assuming that $\sum_{i=0}^n 3^i \leq 3^{n+1}$,
      \begin{enumerate}
        \item Base step: $\sum_{i=0}^0 3^i = 3^0 \leq 3^{0+1} = 3^1$ is true.
        \item Inductive step: assuming $\sum_{i=0}^{n+1} 3^i = \sum_{i=0}^n 3^i + 3^{n+1}$
      \end{enumerate}
      \begin{equation*}
        \begin{split}
          \sum_{i=0}^n 3^i + 3^{n+1} & \leq 3^{n+1} + 3^{n+1}\\
          & \leq 2 \cdotp 3^{n+1}\\
          & \leq 3^{(n+1)+1}
       \end{split}
     \end{equation*}
     so the inductive step holds true as well, so by induction $\sum_{i=0}^n 3^i \leq 3^{n+1}$ for any positive integer $n$.
    % induction stuff https://www.math.ku.edu/~jhart/Induction_Sum.pdf
    % https://math.stackexchange.com/questions/734934/prove-by-induction-sum-i-0n-3i-frac-3n1-12
    \end{solution}

\end{document}