Determining if case 2 applies of the Master Theorem when a=1, b=2, f(n) = logn

30 views Asked by At

I'm learning the master theorem and have the following problem:

T(n) = T(n/2) + log n    
a = 1
b = 2
c = 1
f(n) = log n
Delta = log(1) = 0
    
So the conditions for master theorem are met.

n^Delta = n^0 = 1, which is asymptotically close to f(n) so case 2 applies.

Therefore:    
T(n) in (f(n)logn) = O(logn^2)

I feel that I'm doing something wrong. Can someone tell me if this is correct?

0

There are 0 answers