Resolva as seguintes relações recorrência e notação
. Caso resolva pelo Teorema Mestre, exiba os valores de
e
do teorema.
(a)
(b)
©
(d)
, onde
(e)
(a)
(b)
©
(d)
(e)
Passo 1
A gente tem 5 recorrências para resolver e depois achar a notação big-O (ou Θ). Para as que der pra usar o Teorema Mestre, vamos identificar
,
e
e comparar com
. Para as outras, usaremos métodos diretos (iteração, equação característica etc.).
Passo 2
Para (a)
: aqui
,
e
. Calculamos
Como
Passo 3
Para (b)
: aqui
,
,
. Então
Como
Passo 4
Para ©
: temos
,
, então
Passo 5
Porém
cresce muito mais rápido (é superpolinomial) do que qualquer
. Em uma versão ampliada do Mestre (caso 3) o termo de fora domina, dando
Passo 6
Para (d)
com
, iteramos:
Passo 7
Para (e)
é uma recorrência linear não-homogênea. A parte homogênea é
. Uma solução particular constante é
, então
Resposta
(a) Θ\bigl(n^{\log_3 2}\bigr)
(b) Θ(n\log n)
© Θ\bigl(n^{\tfrac{3}{2}\log n}\bigr)
(d) Θ(n^{c+1})
(e) Θ(2^n)
(b) Θ(n\log n)
© Θ\bigl(n^{\tfrac{3}{2}\log n}\bigr)
(d) Θ(n^{c+1})
(e) Θ(2^n)