113 views

0 votes

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

How to solve this without using master's theorem?

My final result

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

How to solve this without using master's theorem?

My final result

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

## 2 Answers

1 vote

Best answer

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)²)

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)²)

0 votes

**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)) ...**