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


Top Users Sep 2017
  1. Habibkhan

    6338 Points

  2. Warrior

    2220 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,981 questions
33,556 answers
79,367 comments
31,014 users