recategorized by
3,237 views
13 votes
13 votes

Solve the recurrence equations:

  • $T(n)= T( \frac{n}{2})+1$
  • $T(1)=1$
recategorized by

5 Answers

Best answer
22 votes
22 votes
$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 \geq 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.
selected by
3 votes
3 votes
T(n)=T(n/2)+1

Using Master Theorem :

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

T(n)=O(logn)
3 votes
3 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
 

0 votes
0 votes

Here is the answer in this image

Here is the very clear answer in this image. I'm writing this because this is compulsory otherwise I don't find text is important. So you want this answer check this image.

Related questions

14 votes
14 votes
4 answers
2
go_editor asked Dec 10, 2016
2,693 views
Quicksort is ________ efficient than heapsort in the worst case.