MAC0338/lista5.md

1. Mostre que lg (n!) ≥ (n/4) lg n para n ≥ 4 sem usar a formula de Stirling.

Vamos utilzar que $$2 lg \space (n!) \geq (n/2) lg \space n$$ e lebrem que $$ 2 lg \space (n!) = lg \space (n!^2) = lg \space(\prod_{i=0}^{n-1} (n-i) \cdot (i+1)) $$ $$ (n-i) \cdot (i+1) = ni+n-i^2-i$$

Se realizarmos primeira derivada dessa função em $i$ e igualarmos a 0, vamos obter que $n-2i-1 = 0$. Resolvendo essa equaçao e sabendo que a parábola da equação de segundo grau é voltada para baixo, descobrimos que o ponto máximo dessa equação é em $i = \frac{n-1}{2}$. Veja que $i \in [0, n-1]$, calculando o valor da equação nos tremos chegamos a $n$ em ambos o caso. Portanto como o máximo está entre os extremos e nelas o valor é $n$, podemos concluir que,

$$ (n-i) \cdot (i+1) \geq n $$

Usando isso,

$$ 2 \cdot lg \space (n!) \geq 2 \cdot lg \space (\prod_{i=0}^{n-1} n) = 2 \cdot lg \space (n^n) = 2 \cdot n \cdot lg \space (n)$$

$$ lg \space (n!) \geq n \cdot lg \space (n)$$

Se dividirmos a parte da direita dessa inequação por 4 ela continua sendo válida e chegamos onde queríamos.

2. (CLRS 8.1-3) Mostre que não há algoritmo de ordenação baseado em comparações cujo consumo de tempo é linear para pelo menos metade das n! permutações de 1 a n. O que acontece se trocarmos “metade” por uma fração de 1/n? O que acontece se trocarmos “metade” por uma fração de $\frac{1}{2^n}$?

Tenho $n!/2$ folhas na nossa árvore de decisão (note que é uma árvore binária), portanto não pode ter mais que $2^h$ folhas ($h$ é a altura da árvore e é ainda desconhecido). Portanto $$\frac{n!}{2} \leq 2^h$$ Aplicando o $lg$ em anbos os lados, $$h \geq lg \space (n!) - 1$$ E sabendo que $$ lg \space (n!) \geq n \cdot lg \space (n)$$ (pelo exercíco anterior), $$h \geq lg \space (n!) - 1 \geq n \cdot lg \space (n) - 1$$ Ou seja, o número mínimo de comparações será $h$ e como $h$ é limitado inferiormente por $lg \space (n) - 1$, temos que o algorítimo irá realizar no mínimo $\Theta(lg \space (n))$ comparações.