The Gateway to Computer Science Excellence
+8 votes
846 views

Solve the recurrence equations:

  • $T(n)= T( \frac{n}{2})+1$
  • $T(1)=1$
in Algorithms by | 846 views

5 Answers

+11 votes
Best answer
$T(n) = T(n/2) + 1$

$=T(n/4) + 2$

$= T(n/8) + 3$

$\vdots$

$=T(n/{2^k}) + k.$

Recurrence stops when $2^k >= n$.

When $2^k = n,k = \lg n$

So, $T(n) = T(1) + \lg n \\= 1 + \lg n$

PS: Unless explicitly asked for asymptotic bound, we should give exact answers for solutions of recurrence equations.
by
selected by
+2 votes

It is a standard Recurrence for Binary Search :
T(n) = T(n/2) + Θ(1).

T(n)=T(n/2k)+k
base case T(1)=1
k=logn
T(n)= logn+1
 

by
+1 vote
T(n)=T(n/2)+1

Using Master Theorem :

a=1,b=2,k=0,p=0

T(n)=O(logn)
by
0
is is master Theorem case 2a
–2 votes

T(n)=T(n2)+1
use master theorem we get answer as logn

by
–2 votes
It is easy to solve it by using master theoram. apply condition a=b rasied to power k.
by

Related questions

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
52,345 questions
60,513 answers
201,931 comments
95,360 users