\documentclass[12pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{xspace}

\pagestyle{empty}
\setlength{\textwidth}{15cm}
\setlength{\textheight}{24cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\topmargin}{-1.5cm}

\newcommand{\R}{\ensuremath{\mathbb{R}}\xspace}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}\xspace}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}\xspace}
\newcommand{\C}{\ensuremath{\mathbb{C}}\xspace}
\newcommand{\N}{\ensuremath{\mathbb{N}}\xspace}
\newcommand{\sse}{\Longleftrightarrow}
\newcommand{\floor}[1]{\ensuremath{\lfloor{#1}\rfloor}}
\newcommand{\ceil} [1]{\ensuremath{\lceil{#1}\rceil}}
\newcommand{\tdots}{\,.\,.\,} % in place of \ldots
\newcommand{\Oh}{\mathrm{O}}

\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\begin{document}

\begin{center}
{\large
{\bf 
MAC5711 - Análise de Algoritmos \\
}
}
{\em Departamento de Ciência da Computação} \\
Segundo semestre de 2018 \\

\vspace{5mm}
{\large
{\bf Lista 1} \\
% (Valor: 40 pontos)\footnote{Você só precisa entregar as questões
% que tem valor marcado, mac claro que deve fazer todos \risonho} \\
}
% \vspace{5mm}
% Devolução: 17 de março de 1999
\end{center}

\begin{enumerate}
\item Lembre-se que $\lg n$ denota o logaritmo na base 2 de $n$. Usando a definição de notação~$\Oh$, prove que
\begin{enumerate}
  \item $3^n$ não é $\Oh(2^n)$
  \item $n\lg^5 n$ é $\Oh( n^2)$ mas \(n^2\) não é \(\Oh(n\lg^5 n)\)
  \item $\log_{10} n$ é $\Oh(\lg n)$
  \item $n^2 + 10n + 20 \ = \ \Oh(n^2)$
  \item $\ceil{n/3} \ = \ \Oh(n)$
  \item $\lg n \ = \ \Oh(\log_{10} n)$
  \item $n \ = \ \Oh(2^n)$
  \item $n/1000$ não é $\Oh(1)$ 
  \item $n^2/2$ não é $\Oh(n)$
\end{enumerate}

\item Prove ou dê um contra-exemplo para as afirmações abaixo: 
\begin{enumerate}
\item[(a)] $\lg \sqrt{n} \ = \ \Oh(\lg n)$
\item[(b)] Se $f(n) = \Oh(g(n))$ e $g(n) = \Oh(h(n))$ então $f(n)
  = \Oh(h(n))$.
\item[(c)] Se $f(n) = \Oh(g(n))$ e $g(n) = \Theta(h(n))$ então
  $f(n) = \Theta(h(n))$.
\item[(d)] Suponha que $\lg(g(n))>0$ e que $f(n) \geq 1$ para todo
  $n$ suficientemente grande. Neste caso, se $f(n) = \Oh(g(n))$ então
  $\lg(f(n))=\Oh(\lg(g(n)))$. 
\item[(e)] Se $f(n) = \Oh(g(n))$ então $2^{f(n)}=\Oh(2^{g(n)})$. 
\end{enumerate}

\item Prove que \\
(a) $\sum_{i=1}^{n} i^k$ é $\Theta(n^{k+1})$  \hspace{3cm} 
(b) $\sum_{i=1}^{n} \frac{i}{2^i} \leq 2$.

  \item CLRS 3.1-1, 3-1, 3-2, 3-3, 3-4

Vale a pena fazer tudo isso, e até recomendo que seja em grupo. É bom
\emph{aprender} as afirmativas da 3-1 e da 3-4 (não precisa ter as
demonstrações na ponta da língua). A 3-2 e a 3-3 são questões abertas; um bom
jeito de fazer é chutar cada caso, para ver se está sendo formada uma intuição
-- mas é importante conferir com rigor se a intuição está certa.  
\end{enumerate}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
