Same asymptotic growth - Master Theorem

56 Views Asked by At

Given the master theorem:

if a) f(1) = g(1) and b) f(n) = a f(n/b) + g(n),   
then:  
(1) f(n) ∈ Θ(n^c); if a < b^c  
(2) f(n) ∈ Θ(n^c * log n); if a = b^c  
(3) f(n) ∈ Θ(n ^ log b (a); if a > b^c

How can I prove that if h(x) has the same recurrence equation as f(x), but different initial values, they still have the same asymptotic growth? Thanks a lot!

0

There are 0 best solutions below