T(n)=T(n/2)+logn How to solve this without using masters theorem?
in Algorithms edited by
0 votes
0 votes

How to solve this without using master's theorem?

My final result

$(Logn)^2 – 3/2(logn)$
in Algorithms edited by
9 points

2 Answers

1 vote
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


              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)²)
selected by
71 points
0 votes
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)) ...

5 points
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.