T(n)=T(n/2)+logn How to solve this without using masters theorem?
in Algorithms edited by
63 views
0 votes
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)$
in Algorithms edited by
by
7 points
63 views

2 Answers

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

by
5 points
0 votes
0 votes
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
Ask
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.