The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
160 views

Solve the recurrence equations:

  • $T(n)= T( \frac{n}{2})+1$
  • $T(1)=1$
asked in Algorithms by Veteran (99k points) | 160 views

3 Answers

+2 votes
T(n)=T(n/2)+1

Using Master Theorem :

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

T(n)=O(logn)
answered by Loyal (2.6k points)
+1 vote

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

answered by Veteran (21.6k points)
0 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
 

answered by Loyal (4.9k 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

29,066 questions
36,872 answers
91,629 comments
34,760 users