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

How to solve this without using master's theorem?

My final result

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

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
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
5 points