\documentclass[12pt]{article}


\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}


\setlength{\unitlength}{28pt}
\setlength{\textwidth}{15cm}
\setlength{\textheight}{22.5cm}
\setlength{\oddsidemargin}{0.1in}
\setlength{\evensidemargin}{0.1in}

\voffset=-10mm 
%\voffset=-2.5cm
\hoffset=1cm
\newcommand{\p}{\vspace{1.44ex}}

\begin{document}
\begin{center}
{\large \bf MAC5710  Estruturas de Dados -- Lista de exerc\'{\i}cios 1}

(baseados nos livros de Szwarcfiter \& Markenzon e Ziviani)
\end{center}

\begin{enumerate}
\item 
Escrever as seguintes funções em notação $O$:

(a) $3 n^3 + 20 n^2 \log n$

(b) $3 n^n + 5 .  2^n$

(c) $ (n-1)^n + n^{(n-1)}$

(d) $4 n + 2 n \log n$

(e) 34

\item 
O que significa dizer que a função $g(n)$ é $\Omega(h(n))$?
Dê a definição formal.

\item
Indique se as afirmativas abaixo são verdadeiras ou falsas
e justifique sucintamente sua resposta.

(a) $2^{(n+1)} = O(2^n)$

(b) $2^{2n} = O(2^n)$


\item

Responder se é certo ou errado:

(a) Para um dado problema, se a complexidade do melhor caso 
de um algoritmo é $O(n \log n)$,
então a cota inferior deste problema é $\Omega(n \log n)$.

(b) 
A cota inferior de um problema depende 
só do problema.

(c) A cota inferior de um problema pode
mudar com a descoberta de um novo
algoritmo.

(d) A cota superior depende somente do
problema.

(e) A cota superior é sempre não inferior
à cota inferior.


\end{enumerate}

\end{document}

