# Big O problem

Consider the recurrence

T(1)=a

T(n)=cT(n/d)+bn^k, for n a power of d

Iteratively expand T(n) in terms of T(n/d^i) for i=1,2,.... Show that

a) if c > d^k, then T(n) is O(n^logd c)

b) if c = d^k, then T(n) is O(n^k log n)

c) if c < d^k, then T(n) is O(n^k)

https://brainmass.com/computer-science/algorithms/big-o-problem-26321

#### Solution Summary

This solution helps with a software development problem.

$2.19