\documentclass[11pt]{article}

\newcommand{\ignoreNew}{Hoc hoc Larmore Ajoy Datta Priyanka Vemula MANETs
MIS clusterhead clusterheads Amis Spohn Aceves multi Fernandess and Malkhi
subsec subsubsec subsubsection LLL ss subgraph mis funcs tbl cllcl fgr lem
CVP cvp eps polylogarithmic sublinear bcircuit tmis ndes altintrfr altdepth
calS alg nc bcp rcp optdom cond alphacases subtrees calD 
breduced alphatree misdisk maxisdisk dstrbtd
thm clstr subtree subgraphs clstrII clstrIII dom le Folkman indep bigs intra}

\marginparwidth 0pt
\oddsidemargin -0.4in %0pt
\marginparsep 0pt
\topmargin  -0.6in
\textwidth   7.2in%6.5in
\textheight  9.1in

\parskip 1.3ex
\parindent 0ex

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[xdvi,dvips]{graphics}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{array}
\usepackage{float}
\usepackage{dsfont}
\usepackage{xspace}
%\usepackage{figlatex}

\graphicspath{{Figures/}{./}}

\input{preamble}
\input{special}

\newcounter{jump}
%\newcounter{jumpaction}
%\newcounter{jumpfunction}

\newcounter{tbl}
\newcounter{fgr}
\newcounter{prp}
\newcounter{action}
\newcounter{priority}

%\renewcommand{\linecomment}[1]{}
%\renewcommand{\datecomment}[1]{}
%\renewcommand{\bfcomment}[1]{{}}


\renewcommand{\Label}{\label}
\renewcommand{\Ref}{\ref}
\renewcommand{\Refstepcounter}{\refstepcounter}

\renewcommand{\today}{}

\raggedbottom


\title{Ordering Complexity Classes:\\
Problem 3--3 $a$, page 58\\
{\em Cormen, Leiserson, Rivest, Stein}:
Second Edition}


\begin{document}

\maketitle

We write $f(n)\equiv g(n)$ to mean that $f(n)=\Theta(g(n)$, and we write
$f(n)\ll g(n)$ to mean that $f(n)=O(g(n))$ but $g(n)\ne\Theta(g(n))$.

$\lg(\lg^*n)$ LL

$2^{\lg^*n}$ LL

$\parend{\sqrt{2}}^{\lg n}$ EE

$n^2$ PP

$n!$ EE

$\parend{\lg n}!$ PP


$\parend{\threehalves}^n$ EE

$n^3$ PP

$\lg^2n$ LL

$\lg\parend{n!}$ PP

$2^{2^n}$ EE

$n^{1/\lg n}$ CC


$\ln \ln n$ LL

$\lg^*n$ LL

$n\cdot 2^n$ EE

$n^{\lg \lg n}$ PP

$\ln n$ LL

$1$ CC


$2^{\lg n}$ PP

$\parend{\lg n}^{\lg n}$ LP

$e^n$ EE

$4^{\lg n}$ PP

$(n+1)!$ EE

$\sqrt{\lg n}$ LL


$\lg^*\parend{\lg n}$ LL

$2^{\sqrt{2\lg n}}$ EE

$n$ PP

$2^n$ EE

$n\lg n$ PP

$2^{2^{n+1}}$ EE
\end{document}
