
\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


%%%%%%%%  ASYMPTOTIC NOTATION %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% HERE ARE SOME PROBLEMS THAT DIDN''T SEEEM TO BELONG
%%% ANYWHERE ELSE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}
\problem %source: spring00 ps6
\textbf{Asymptotic notation}
% problem 4, problem set 5, fall 1997

Given that $f(x) = O(g(x))$, prove or disprove the following:

\bparts
\ppart
$2^{f(x)} = O(2^{g(x)})$

\solution{%
  The above does not hold. Let $f(x) = 2x$ and $g(x) = x$. Then $f(x)
  = O(g(x))$. Now $2^{f(x)} = 2^{2x} = 4^x$, and $2^{g(x)} = 2^x$, and
  $4^x\neq O(2^x)$. Indeed, $\frac{4^x}{2^x} = 2^x$, so the ratio
  grows without bound as $x$ grows~---~it is not bounded by a constant. %
  }

\ppart 
$f(x)^2 = O(g(x)^2)$

\solution{%
  The above does hold.  Since $f(x) = O(g(x))$, $\exists x_0,c$ such
  that $\forall x \geq x_0, |f(x)| \leq cg(x)$.  So, $\forall x \geq
  x_0, f(x)^2 \leq c^2g(x)^2$.  Therefore, there exist $x_0' = x_0$
  and $c' = c^2$ such that $\forall x \geq x_0', f(x)^2 \leq
  c'g(x)^2$.  So $f(x)^2 =
  O(g(x)^2)$. %
  }

\eparts


  \problem \textbf{Asymptotic notation} \\
  For each pair of functions $(f(n), g(n))$ in the table below,
  indicate whether the statement at the top of the column is true
  (e.g., whether $f(n) = O(g(n))$).  Assume $k\geq 1$, $\epsilon > 0$,
  and $c > 1$ are constants. Your answer should be in the form of a
  table with ``yes'' or ``no'' in each box.
  \begin{equation*}
    \begin{array}{|cc|*{3}{c|}}
      \hline
      f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
      \Theta(g(n)) \\\hline\hline
      \log^k n & n^\epsilon &&&\\\hline
      n^k & c^n &&&\\\hline
      \sqrt{n} & n^{\sin n} &&&\\\hline
      2^n & 2^{n/2} &&&\\\hline
      \log(n!) & \log(n^n) &&&\\\hline
    \end{array}
  \end{equation*}

  \solution{
    \newcommand\y{\text{yes}}
    \newcommand\n{\text{no}}
                                %
    \begin{equation*}
      \begin{array}{|cc|*{3}{c|}}
        \hline
        f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
        \Theta(g(n)) \\\hline\hline
        \log^k n & n^\epsilon & \y & \n & \n \\\hline
        n^k & c^n & \y & \n & \n \\\hline
        \sqrt{n} & n^{\sin n} & \n & \n & \n\\\hline
        2^n & 2^{n/2} & \n & \y & \n \\\hline
        \log(n!) & \log(n^n) & \y & \y & \y \\\hline
      \end{array}
    \end{equation*}

    Following are some hints on deriving the table above:\\
    (a) See notes on $O$-notation. (to appear)\\
    (b) Polynomial growth versus exponential growth. (See Theorem 3.6,
    Lecture 9, Fall97.)\\
    (c) When $n$ is a multiple of $\pi$, $n^{\sin n}=1$, so no
    constant times 1 will bound $\sqrt n$ as $n$ ranges over
    multiples of $\pi$. When $n$ is of the form $2k'\pi + \pi/2$,
    for some integer $k'$, then $n^{\sin n}=n$ and $\frac{n}{\sqrt n} =
    \sqrt n$ grows without bound as $k'$ increases.\\
    (d) $\frac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
    grows -- it is not bounded by a constant.\\
    (e) See Rosen \S 1.8 Ex. 61,62\\
    }

  \problem \textbf{Asymptotic notation} \\
  You don't need to give proofs for this problem.

  \begin{problemparts}
    \problempart Find functions $f_1$, $f_2$, $g_1$, and $g_2$, such
    that
    \begin{align*}
      f_1(n) &= \Theta(f_2(n)),\\
      g_1(n) &= \Theta(g_2(n)),\\      
      \neg [f_1(g_1(n)) &= \Theta(f_2(g_2(n)))].\\
    \end{align*}

    \solution{$f_1(n) = f_2(n) = 2^n$, $g_1(n) = n$, $g_2(n) = 2n$.}
    

    \problempart Find functions $f$ and $g$ such that
    \begin{gather*}
      f(n) = O(g(n)), \text{ but } \neg [g(n) = O(f(n))];\\
      f(g(n)) = \Theta(g(f(n))).
    \end{gather*}

    \solution{$f(n) = n^2$, $g(n) = n^3$.}

      
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      f(g(n)) &= O(g(f(n))),  &\text{ but } &&\neg [g(f(n)) &=
      O(f(g(n)))].\\
    \end{alignat*}

    \solution{$f(n) = n^2$, $g(n) = 2^n$.}
    
    
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      g(f(n)) &= O(f(g(n))), &\text{ but } &&\neg [f(g(n)) &= O(g(f(n)))].\\
    \end{alignat*}
    
    \solution{$f(n) = 2^n$, $g(n) = 2^{2 n}$. Then $f(g(n)) = 2^{2^{2
          n}}$, while $g(f(n)) = 2^{2^{n+1}}$.}
  \end{problemparts}

  

  \problem \textbf{Stirling's formula and asymptotic notation} \\
  Let $\lambda$ be a constant, $0 < \lambda < 1$. Suppose we start
  with integers from 1 to $n$, and we would like to pick out a
  fraction $\lambda n$ of them. We will use Stirling's formula to help
  us approximate the number of ways to do this.
  
  First, let's see how many ways there are to make an ordered sequence
  of $\lambda n$ numbers between $1$ and $n$. We will use the product
  rule: There are $n$ possibilities for the first number, $n-1$ for
  the second one, $n-2$ for the third, etc. The total number of
  sequences is
  \begin{equation*}
    n \cdot (n-1) \cdot (n-2) \cdots (n - \lambda n + 1) =
    \frac{n \cdot (n-1) \cdots 2 \cdot 1}{(n-\lambda n) \cdot
      (n-\lambda n-1) \cdots 2 \cdot 1}
    = \frac{n!}{(n-\lambda n)!}.
  \end{equation*}

  Now let us ignore order, i.e., let's count subsets of size $\lambda
  n$ instead of sequences of that size. A set of size $\lambda n$ can
  be ordered in
  \begin{equation*}
    \lambda n \cdot (\lambda n - 1) \cdot (\lambda n - 2) \cdots 2
    \cdot 1 = (\lambda n)!
  \end{equation*}
  ways ($\lambda n$ choices for which element to put first, $\lambda n
  - 1$ for which to put second, etc.). Therefore, the number of
  subsets of size $\lambda n$ is
  \begin{equation*}
    \frac{n \cdot (n-1) \cdot (n-2) \cdots (n - \lambda n +
      1)}{(\lambda n)!} =
    \frac{n!}{(\lambda n)! (n-\lambda n)!}.
  \end{equation*}
  Define
  \begin{equation*}
    f_\lambda(n) = \frac{n!}{(\lambda n)! (n-\lambda n)!}.
  \end{equation*}
  
  In this problem, you will need to estimate $f_\lambda(n)$
  for large values of $n$, while $\lambda$ stays constant.

  \begin{problemparts}
    \problempart
    Show that
    \begin{equation*}
       f_\lambda(n) = \Theta(2^{n H(\lambda)}/\sqrt{n}),
    \end{equation*}
    where
    \begin{equation*}
      H(\lambda) = - \lambda \log_2 \lambda - (1-\lambda)
      \log_2(1-\lambda).
    \end{equation*}
    Remember that you have to prove both an upper and a lower bound.

    \solution{
      First, let's show the upper bound, i.e., that $f_\lambda(n) =
      O(2^{n H(\lambda)}/\sqrt{n})$.
      \begin{align*}
        \frac{n!}{(\lambda n)! (n - \lambda n)!} &=
        O\left(\frac{n^{1/2} (n/e)^n}{n \sqrt{\lambda (1-\lambda)} (\lambda
          n/e)^{\lambda n} ((1-\lambda) n/e)^{(1-\lambda) n}}\right)
        \\&= O\left(\frac{(n/e)^n}{n^{1/2} (n/e)^n \lambda^{\lambda n}
          (1-\lambda)^{(1-\lambda) n}}\right)
        \\&= O\left(\frac{1}{n^{1/2} (\lambda^\lambda
          (1-\lambda)^{1-\lambda})^n}\right)
        \\&= O\left(\frac{2^{n H(\lambda)}}{n^{1/2}}\right).
      \end{align*}
      Note that we used Stirling's formula to both put an upper bound
      on $n!$ and a lower bound on $(\lambda n)! (n - \lambda n)!$.
      
      We can similarly show the lower bound, i.e., that $2^{n
        H(\lambda)}/\sqrt{n} = O(f_\lambda(n))$. We would use
      Stirling's formula to get a lower bound on $n!$ and an upper
      bound on $(\lambda n)! (n - \lambda n)!$.
      }
    
    
    \problempart (optional) Let $n = 100$ and $\lambda = 0.3$. Compute $\log_2
    f_\lambda(n)$. Also, compute the logarithm base $2$ of the
    approximation of $f_\lambda(n)$ that you proved in part~(a). Note
    that the first task would most likely require a computer program,
    while the second can be done with a regular pocket calculator.

    \solution{
      \begin{align*}
        \log_2 f_{0.3}(100) &= 84.6027,\\
        \log_2 (2^{100\cdot H(0.3)}/\sqrt{100}) &= 84.8072.
      \end{align*}
      }
    

    \problempart (optional) If we have a number $x$ and an approximation $x'$, we
    say that the \emph{relative error} of the approximation is
    $\left|\frac{x' - x}{x}\right|$. Compute the relative error of the
    approximation you obtained in part~(b).

    \solution{
      The relative error is
      \begin{equation*}
        \frac{84.8072 - 84.6027}{84.8072} = 0.00241135.
      \end{equation*}
      }

    
    \problempart Prove the following statement: If $f$ and $g$ are
    positive-valued functions such that $f(n) = \Theta(g(n))$, and
    $\lim_{n\to\infty} g(n) = \infty$, then $\log f(n) \sim \log g(n)$
    (the base of the logarithm is arbitrary).
    
    \solution{     
      We have,
      \begin{equation*}
        \frac{\log f(n)}{\log g(n)} =
        \frac{\log g(n) -\log g(n) + \log f(n)}{\log g(n)}
	= \frac{\log g(n) + \log \frac{f(n)}{g(n)}}{\log g(n)}
        = 1 + \frac{\log \frac{f(n)}{g(n)}}{\log g(n)}
      \end{equation*}
      We are given that $f(n)=\Theta(g(n))$, therefore
      $\lim_{n\to\infty}\frac{f(n)}{g(n)}$ is bounded (away from 0, as
      otherwise $\lim_{n\to\infty}\frac{g(n)}{f(n)}$ would be unbounded
      i.e. $g\neq O(f)$), and moreover,
      $\lim_{n\to\infty}\log\frac{f(n)}{g(n)}$ is bounded. We are also
      given that $\lim_{n\to\infty} g(n) = \infty$, therefore
      $\lim_{n\to\infty} \log g(n) = \infty$. Thus, 
      \begin{equation*}
        \lim_{n\to\infty} \frac{\log f(n)}{\log g(n)} =
        \lim_{n\to\infty} (1 + \frac{\log \frac{f(n)}{g(n)}}{\log g(n)})
        = 1 + \frac{\lim_{n\to\infty}\log
      \frac{f(n)}{g(n)}}{\lim_{n\to\infty} \log g(n)}
        = 1.
      \end{equation*}
      i.e. $\log f(n) \sim \log g(n)$.


%      It is easy to show, given $f(n) = \Theta(g(n))$, that there
%      exist constants $c_1$ and $c_2$, with $0 < c_1 \leq c_2$, and an
%      integer $n_0$, such that
%      \begin{equation*}
%        \frac{f(n)}{g(n)} \in [c_1, c_2]
%      \end{equation*}
%      for all $n > n_0$.
%      
%      Let $h(n) = \log g(n)$. Since $\lim_{n\to\infty} g(n) = \infty$,
%      we must have $\lim_{n\to\infty} h(n) = \infty$. Consequently,
%      \begin{equation*}
%        \lim_{n\to\infty} \frac{1}{h(n)} = 0.
%      \end{equation*}

%      We have
%      \begin{equation*}
%        \frac{\log f(n)}{\log g(n)} =
%        \frac{\log g(n) + \log \frac{f(n)}{g(n)}}{\log g(n)}
%        = 1 + \frac{\log \frac{f(n)}{g(n)}}{h(n)}
%        = 1 + \ell(n),
%      \end{equation*}
%      where $\ell(n) = \frac{\log \frac{f(n)}{g(n)}}{h(n)}$.

%      For all $n>n_0$, we have
%      \begin{equation*}
%        \ell(n) =
%        \frac{\log \frac{f(n)}{g(n)}}{h(n)}
%       \in \left[\frac{\log c_1}{h(n)}, \frac{\log c_2}{h(n)}\right].
%      \end{equation*}
%      Clearly, $\log c_i$ is a constant for each $i\in \{1, 2\}$ (note
%      that $c_i > 0$). Therefore,
%      \begin{equation*}
%        \lim_{n\to\infty} \frac{\log c_i}{h(n)} =
%        \log c_i \times \lim_{n\to\infty} \frac{1}{h(n)}
%        = 0.
%      \end{equation*}

%      It follows that
%      \begin{equation*}
%        \lim_{n\to\infty} \ell(n) = 0.
%      \end{equation*}
%      Consequently,
%      \begin{equation*}
%        \lim_{n\to\infty} \frac{\log f(n)}{\log g(n)} =
%        \lim_{n\to\infty} (1 + \ell(n))
%        = 1 + \lim_{n\to\infty} \ell(n)
%        = 1.
%      \end{equation*}
%      Thus $\log f(n) \sim \log g(n)$.
      }
  \end{problemparts}


\end{problems}

\end{document}