Solving this recurrence relation: T(n) = 2 T(n/2) + f(n)

Question

How do we solve this recurrence relation generically?

For example, we can say something like: if f(n) = omega(n^1+epsilon), then T(n) = f(n).  etc?

Answer 1

Using Master's Theorem:

1.) n^{log  _b a}   = n ^{log  ₂ 2}    = n   ||  For instance, f(n) is n*log^kn . Then the Time Complexity of the recurrence relation would be Theta( n*log^k+1n). 

2.)  n^log  _b a   = n ^{log  ₂ 2}    = n  ||   For instance, f(n) is O(n^1-e). Then the Time Complexity for the recurrence relation would be Theta(n). 

3.)  n^log  _b a   = n ^{log  ₂ 2}    = n  ||  For instance, f(n) is omega(n^1+e). Then the Time Complexity for the recurrence relation would be Theta(f(n)). 

Answer 2

Because of the format of the problem, you could use master theorem to find a generic solution for any given f(n). In the format T(n) = a*T(n/b) + c*f(n), we can assign k = log_ba such that:

If f(n) = omega(n^k), T(n) = theta (f(n))

If f(n) = o(n^k) then T(n) = theta(n^k)

If f(n) = theta(n^k) then T(n) = theta(f(n) * log n)