113 views
$T(n)=T(n/2)+logn$

How to solve this without using master's theorem?

My final result

$(Logn)^2 – 3/2(logn)$

Using substitution method :

T(n)=T(n/2)+log n

=T(n/2²) + log n/2 + log n

=T(n/2³) + log n/2² + log n/2 + log n

In general we can say

=T(n/2powK) +log n/2pow(K-1) + log n/2pow(K-2) +....+ log n/2pow(K-K)       ....eq1

Now , n/2powK =1

n=2powK

K=logn base 2

Put in eq 1,we get

=T(1) + log2 + log 2² + log 2³+ .......+ log 2powK

=1+ log2 + 2log2 +3log2 +....+ Klog2

=1 + log2( 1+2+3+.....K)

Approx =K(K+1) /2

=O( K²)

=O ( log n. log n)

=O( (log n)²)
by
71 points

Another approach is to use the Master Theorem ...

For most recurrences it is applicable and provides the answer very fast. It basically gives you three categories and then the answer falls out.

Given a recurrence of the form T (n) = aT (n/b) + f (n) we look for a,b, and f(n).

In your case we have a=1, b=2, f(n)=log n.

Therefore (you have to look at the referenced links) we fall into Case 2, where f(n) is in Theta(n^(log_b(a-eps)) log^k(n)) = Theta(n^0 log(n)),

then the Master Theorem states that T(n) is in Theta(n^(log_b(a-eps)) log^(k+1)(n)) = Theta(log^2(n)) ...

by
5 points