\documentclass{article}
\usepackage{ccfonts,fullpage,amssymb,amsmath}
\renewcommand{\today}{~}
\renewcommand{\bfseries}{\scshape}
\title{CSC165 Fall 2009\\
Assignment 3\\
{\large due Friday December 4th, 10pm}}
\begin{document}
\maketitle

The aim of this assignment is to give you more practice with big-Oh
proofs and algorithm complexity.  Your solution
should be submitted as a PDF file \verb+a3.pdf+ to the CDF submission
site:
\begin{verbatim}
https://www.cdf.toronto.edu/students/
\end{verbatim}
You are welcome to work with up to one other partner from this course
on this assignment.  You indicate a partnership by each partner
submitting the file \texttt{partnerA3} to the CDF submission site.
The content of the file should be the CDF userid of your partner.

\begin{enumerate}
\item Use the proof structure from this course to \textbf{prove} or
  \textbf{disprove} the following claims.  Please note that some of
  the claims are \textbf{false}, and should be disproved.
  \begin{enumerate}
  \item Define $f(n)=3n^3 + 5n$ and $g(n) = n^4 + 2n^2 +7$.  Claim: $f\in\mathcal{O}(g)$.
  \item Use the same $f$ and $g$ from the previous question.  Claim: $g\in\mathcal{O}(f)$.
  \item Define $f(n)=7^n + \ln(n)$ and $g(n) = n^3 + n$.  Claim:  $g \in\Omega(f)$.
  \item Let $\mathcal{F} = \{f:\mathbb{N}\mapsto \mathbb{R}^{\geq
      0}\}$.  Define $\min(f,g)$ as $\forall n\in\mathbb{N},
    \min(f,g)(n) = \min(f(n), g(n))$.  Claim:
    \begin{eqnarray*}
      \forall f, g, h\in\mathcal{F}, f \in\Omega(h) \wedge
      g\in\Omega(h) \Rightarrow \min(f,g) \in\Omega(h)
    \end{eqnarray*}
  \item Does it work the other way?  Define $\max(f,g)$ as $\forall
    n\in\mathbb{N}, \max(f,g)(n) = \max(f(n),g(n))$. Claim:
    \begin{eqnarray*}
      \forall f, g, h\in\mathcal{F}, \max(f,g) \in \Omega(h)
      \Rightarrow f\in\Omega(h) \vee g \in\Omega(h)
    \end{eqnarray*}
  \end{enumerate}
\item Choose one of the four definitions of $f$ below so that the
  worst-case running time of the algorithm DL is bounded above and
  below by the function you chose, that is $W_{\text{DL}} \in
  \mathcal{O}(f) \wedge W_{\text{DL}}\in\Omega(f)$.  Prove that your
  bound is correct.
  \begin{equation*}
    f(n) = \log_2(n)\qquad f(n) = \sqrt{n} \qquad f(n) = n\qquad f(n)
    = n^2
  \end{equation*}
\begin{verbatim}
def DL(n) :
   i = 0
   while 2**i < n : i += 1
   return i
\end{verbatim}
\end{enumerate}
\end{document}
