MO417 - Prova I1

Gabarito e critérios de correção:

Em cada passo, o elemento a ser "mandado para baixo" está em negrito.

1 2 3 4 5 6 7 8 9

1 2 3 9 5 6 7 8 4

1 2 7 9 5 6 7 8 9

1 9 7 8 5 6 3 2 4

9 8 7 4 5 6 3 2 1
Como na recorrência há um termo independente igual a n, temos T(n) = Ω(n). Vale a pena tentar T(n) ≤ cn pelo método da substituição. Acaba dando certo, pois obtemos:

T(n) = T(n/2) + T(n/3) + T(n/9) + n ≤ cn/2 + cn/3 + cn/9 + n = (17c/18 +1)n.

Para fazer isto ser menor ou igual a cn, basta tomar c ≥ 18. Assim, concluimos que T(n) = Θ(n).
- (lg n)^{n/lg n} contra 2ⁿ. Aplicando lg dos dois lados, fica
  
  (n lg lg n) / lg n contra n.
  
  Ora, como lg lg n = o(lg n), temos (lg n)^{n/lg n} = o(2ⁿ).
- sqrt(lg n) vs. n^{1/lg n}. Aplicando lg dos dois lados, fica
  
  (lg lg n)/2 vs. (1/lg n)lg n = 1.
  
  Como 1 = o(lg lg n), temos n^{1/lg n} = o(sqrt(lg n)).
- lg(lg^*n) contra lg^*(lg n). Aqui era preciso observar que lg^*lg n = lg^*n - 1. Se m = lg^*n, estamos portanto comparando
  lg m contra m - 1.
  
  O lado direito cresce mais rápido, o que mostra que lg(lg^*n) = o(lg^*(lg n)).
Aqui pode-se usar o Radix Sort que ordena n números de b bits em tempo Θ((b/r)(n+2^r)). No caso, b = 4 lg n, pois os números estão entre 0 e n⁴-1. Escolhendo r = lg n, temos complexidade

Θ((4 lg n)/(lg n) (n + 2^{lg n})) = Θ(4(n + n)) = Θ(n).

A definir.