Resolva as seguintes relações recorrência e notação O. Caso resolva pelo Teorema Mestre, exiba os valores de a, b e d do teorema.
(a) T(n)=2 T(n / 3)+1
(b) T(n)=7 T(n / 7)+n
© T(n)=49 T(n / 25)+n^3 / 2 log n
(d) T(n)=T(n-1)+n^c, onde c >= 1
(e) T(n)=2 T(n-1)+1

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 a, b e f(n) e comparar com n^logb a. Para as outras, usaremos métodos diretos (iteração, equação característica etc.).

Passo 2

Para (a) T(n)=2T(n/3)+1: aqui a=2, b=3 e f(n)=1=n^0. Calculamos
n^logb a=n^log3 2
Como f(n)=O(n^log3 2-varepsilon) com varepsilon=log3 2>0, cai no caso 1 do Teorema Mestre e
T(n)=Thetal(n^log3 2r)

Passo 3

Para (b) T(n)=7T(n/7)+n: aqui a=7, b=7, f(n)=n=n^1. Então
n^logb a=n^log7 7=n^1
Como f(n)=Theta(n^logb a), é o caso 2 do Mestre e
T(n)=Theta(nlog n)

Passo 4

Para © T(n)=49T(n/25)+n^32log n: temos a=49, b=25, então
n^logb a=n^log2549=n^log 49log25=n^log7log5approx n^1.21

Passo 5

Porém f(n)=n^32log n cresce muito mais rápido (é superpolinomial) do que qualquer n^1.21. Em uma versão ampliada do Mestre (caso 3) o termo de fora domina, dando
T(n)=Thetal(n^tfrac32log nr)

Passo 6

Para (d) T(n)=T(n-1)+n^c com c>=1, iteramos:
T(n)=T(0)+ sumk=1^n k^c =Thetal(sumk=1^n k^cr)=Theta(n^c+1)

Passo 7

Para (e) T(n)=2T(n-1)+1 é uma recorrência linear não-homogênea. A parte homogênea é Th(n)=C2^n. Uma solução particular constante é Tp=-1, então
T(n)=C2^n-1=Theta(2^n)

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)

Exercícios relacionados