The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
274 views
1) T(n)=T(n-1)+1/n.
2) T(n)=T(n-1) +1/log(n)

3)T(n)=3T((n/3) - 2)+n/2.
4)T(n)=T(n/2)+T(n/4)+T(n/8)+n.
Use Masters theorem
asked in Algorithms by Active (1.5k points)
edited by | 274 views
I dont think master theorem can be applied for this..for the first one it just a harmonic series it will be O(logn).Try subsitution method.

3 Answers

+1 vote

Question 1: Master Theorem not possible since b=1, which is not greater than 1.
Question 2: Master Theorem not possible since b=1, which is not greater than 1.
Question 3:
T(n)=3T( (n/3) - 2 ) +n/2 = 3T((3n-6)/3)+n/2 = 3T(3(n-2)/3)+n/2 = 3T((n-2))+n/2
Now, Master Theorem not possible since b=1, which is not greater than 1.

Question 4: T(n)=T(n/2)+T(n/4)+T(n/8)+n

Roughly, T(n) can be written as T(n)<T(n/2)+T(n/2)+T(n/2)+n, which can be further reduced to
T(n)<3T(n/2) + n
Now, a = 3, b=2, k=1, p=0
Clearly, a > bk i.e. 3>21.

So, Case 1 satisfies. Therefore, T(n)=Theta(nlg3) = Theta(n1.584962...) = Theta(n)

I hope it helps. :)

answered by (21 points)
0 votes
t(n)=t(n/2)+t(n/4)+t(n/8) +n;

the above equation can be reduced to

T(n)<3T(n/2)+n

here a=3;b=2

so

a>b

hence by masters theorem T(n)=θ(n^log3 to base 2)
answered by Junior (621 points)
0 votes
3.) Is it O(nlog n ) ?
answered by (287 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,138 questions
36,959 answers
92,024 comments
34,803 users