\batchmode








\documentstyle[11pt,psfig,epsf,landscape,twoside,color]{article}
\makeatletter

\pagestyle{myheadings}

%
\evensidemargin 35pt

%
\setcounter{secnumdepth}{0}

%

\setlength{\oddsidemargin}{0in}
%
\setlength{\textwidth}{6.5in}

%


\setlength{\topmargin}{-0.5in}
%
\setlength{\headheight}{0.25in}
%
\setlength{\headsep}{0.25in}
%
\setlength{\textheight}{8.5in}

%

\setlength{\parindent}{0in}

%
\setlength{\parskip}{\medskipamount}

%



%



%


%






%

\newlength{\hlessmm}
\setlength{\hlessmm}{\textwidth}
\addtolength{\hlessmm}{-2em}

\newlength{\hlessmmmm}
\setlength{\hlessmmmm}{\textwidth}
\addtolength{\hlessmmmm}{-4em}

%



%



%




%







\outer

\outer

{\obeyspaces\gdef {\ }}

%



 

%
\newlength{\illuswidth}
\setlength{\illuswidth}{\textwidth}
\addtolength{\illuswidth}{-7pt}

%


%



%


%



%


%








%














\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{-0.2in}

%



%



\newcommand {\evalsto}{$\Longrightarrow$}

\newcommand {\hstrut}[1]{\hspace*{#1}}

\newcommand {\vstrut}[2]{\rule[#1]{0in}{#2}}

\newcommand {\hm}{\hspace*{1em}}

\newcommand {\hmm}{\hspace*{2em}}

\newcommand {\hmmm}{\hspace*{3em}}

\newcommand {\hmmmm}{\hspace*{4em}}

\newenvironment {tightlist}%
{\begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
}
}%
{\end{list}
}

\newcommand {\cf}{\footnotesize\tt}

\newcommand {\IP}{$\bullet$}

\newcommand {\goesto}{$\longrightarrow$}

\def\beginlisp{%
  \begin{minipage}[t]{\linewidth}
  \begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \obeyspaces
  \obeylines \footnotesize\tt}

\def\endlisp{%
  \end{list}
  \end{minipage}
  }

\def\psfileprefix{/usr/nikhil/parle/}

\def\illustration#1#2{
\vbox to #2{\vfill\special{psfile=\psfileprefix#1.ps hoffset=-72 voffset=-45}}}

\newcommand {\closure}[2]{%
\begin{tabular}[t]{l}
\raisebox{-1.5ex}{%
  \setlength{\unitlength}{0.2ex}
  \begin{picture}(25,15)(0,-7)
   \put( 5,5){\circle{10}}
   \put( 5,5){\circle*{1}}
   \put( 5,5){\vector(0,-1){10}}
   \put(15,5){\circle{10}}
   \put(15,5){\circle*{1}}
   \put(15,5){\vector(1,0){12}}
  \end{picture}}
  \fbox{\footnotesize #2} \\ 
%
\hspace*{0.8ex} \fbox{\footnotesize #1}
\end{tabular}
}

\newcommand {\proc}[2]{%
\begin{tabular}{l}
params: #1 \\ 
body: #2 \\ 
\end{tabular}
}

\newcommand {\psetheader}[2]{%
\markboth{6.001, #1---#2}{6.001, #1---#2}
\begin{center}
MASSACHVSETTS INSTITVTE OF TECHNOLOGY \\ 
Department of Electrical Engineering and Computer Science \\ 
6.001---Structure and Interpretation of Computer Programs \\ 
#1 \\ 
\medskip
{\bf #2}
\end{center}
}

\newcommand {\problem}[1]{{\bf #1}}

\newcommand {\key}[1]{\fbox{{\sc #1}}}

\newcommand {\ctrl}{\key{ctrl}--}

\newcommand {\shift}{\key{shift}--}

\newcommand {\run}{\key{run} \ }

\newcommand {\runkey}[1]{\run \key{#1}}

\newcommand {\extend}{\key{extend} \ }

\newcommand {\kkey}[1]{\key{k$_{#1}$}}

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\def\itemx{\vspace{-0.1in}\item}

\def\ANSWER#1{{\color{red} #1}}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
\setcounter{secnumdepth}{0}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline686: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline688: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{tabular}{p{3in}p{3in}}
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(cond (<pred1> <expr1>)
      (<pred2> <expr2>)
             ...
      (<predN> <exprN>)
      (else    <exprE>))

\end{list}
\end{minipage} 
} &
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
Example:  (define (sign x) 
            (cond ((> x 0) 1)
                   (< x 0) -1) 
                   (else 0))

\end{list}
\end{minipage} 
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline694: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{% latex2html id marker 696
$\theta(\log n)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline696: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{% latex2html id marker 698
$\theta(1)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline698: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline700: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline702: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline704: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Rightarrow$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline706: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline708: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Rightarrow$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline710: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline712: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{tabular}% latex2html id marker 191
{|l|c|c|c|c|}
\hline
Name & $\theta$ notation & n = 2 & n = 10 & n = 100 \\ 
\hline
Constant & $\theta(1)$ & 1 & 1 & 1 \\ 
Logarithmic & $\theta(\log n)$ & 1 & 3.33 & 6.66 \\ 
Linear & $\theta(n)$ & 2 & 10 & 100 \\ 
Quadratic & $\theta(n^2)$ & 4 & 100 & 10,000 \\ 
Exponential & $\theta(2^n)$ & 4 & 1024 & $\approx 1.26 \times 10^{30}$\\ 
\hline
\end{tabular}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$4 \times
10^{11}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline730: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline738: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline740: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Theta(f(n))$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline742: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n)= \Theta(f(n))$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline744: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$k_1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline746: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$k_2$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline748: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}k_1 f(n) \leq R(n) \leq k_2 f(n)\end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n) = \Theta(f(n))$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline758: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n) = 6$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline760: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{% latex2html id marker 762
$\theta(1) \;\;\;\;\;\; 1\cdot 1 \le 6 \le 6\cdot 1 \;\;\; 
\forall n > 0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline762: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n) = n^2 + 3$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline764: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{% latex2html id marker 766
$\theta(n^2) \;\;\;\;\;\; 1\cdot n^2 \le n^2+3 \le 2\cdot n^2 \;\;\; 
\forall n > 2$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline766: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n)  = 6n^3 + 3n^2 + 7n + 100$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline768: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{% latex2html id marker 770
$\theta(n^3) \;\;\;\;\;\; 1\cdot n^3 \le 6n^3+3n^2+7n+100 \le 7\cdot n^3 \;\;\; 
\forall n > 100$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline770: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n) = 5 \cdot \log(n^6)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline772: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{% latex2html id marker 774
$\theta(log(n)) \;\;\;\;\;\; 1\cdot \log(n) \le 5 \cdot \log(n^6) \le 40\cdot \log(n) \;\;\; 
\forall n > 1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline774: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(n) = 2^{3n + 7}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline776: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{% latex2html id marker 778
$\theta(8^n) \;\;\;\;\;\; 1\cdot 8^n \le 2^{3n+7} \le 2^8\cdot 8^n \;\;\; 
\forall n > 0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline778: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{tabular}% latex2html id marker 205
{p{4in}p{2in}}
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (fact1 n)
  (if (= n 1)
       1
       (* n (factorial (- n 1)))))
\null
\null

\end{list}
\end{minipage} 
} & 
{
Time = {\color{red} $\theta(n)$} 

Space = {\color{red} $\theta(n)$}
}
\\ 
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (fact2 n)
   (define (helper cur k)
       (if (= k 1)
           cur
           (helper (* cur k) (- k 1))))
   (helper 1 n))
\null
\null

\end{list}
\end{minipage} 
} & 
{
Time = {\color{red} $\theta(n)$} 

Space = {\color{red} $\theta(1)$}
} \\ 
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (fib1 n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib1 (- n 1))
                  (fib1 (- n 2))))))
\null
\null

\end{list}
\end{minipage} 
} &     
{
Time = {\color{red} $\theta(2^n)$} 

Space = {\color{red} $\theta(n)$}
} \\ 
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (fib2 n)
    (define (fib-iter a b count)
       (if (= count 0)
           b
           (fib-iter (+ a b) a (- count 1))))
 (fib-iter 1 0 n))
\null
\null

\end{list}
\end{minipage} 
} &
{
Time = {\color{red} $\theta(n)$} 

Space = {\color{red} $\theta(1)$}
}
\end{tabular}
}

\stepcounter{section}

\end{document}
