%\input{params}
\documentclass[11pt,twoside]{article}

\usepackage{graphics}
\newcommand{\nand}{|}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\printlayout
\askaboutsolutions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut7}
\newcommand{\tutnum}{7}
\newcommand{\tutdate}{October 20, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\handout{miniquiz4}{Mini-Quiz 6}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item %
  (modified from Rosen, Section 1.8, Problem 13) %
  Show that $2^n$ is $O(4^n)$ but that $4^n$ is not $O(2^n)$.

  
\solution{
 \textbf{Solution:}
 Since $2^n < 4^n$ for all $n > 0$, it follows that $2^n$ is $O(4^n)$. However, if $4^n$ were $O(2^n)$, then for some constant, $C$, $4^n \leqslant C.2^n$ for all sufficiently large $n$. This says that $C \geqslant (4/2)^n$ for all sufficiently large $n$, which is impossible. Hence $4^n$ is not $O(2^n)$.  	
}

  \vspace*{3in}

\end{enumerate}

\end{document}











