GATE CSE
First time here? Checkout the FAQ!
x
0 votes
194 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.3k points)  
edited by | 194 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 (549 points)  
0 votes
3.) Is it O(nlog n ) ?
answered by (159 points)  


Top Users Jul 2017
  1. Bikram

    3960 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1848 Points

  4. joshi_nitish

    1654 Points

  5. Arjun

    1290 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1100 Points

  8. Shubhanshu

    1052 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    702 Points


24,018 questions
30,955 answers
70,327 comments
29,337 users