MadeEasy Subject Test: Algorithms - Recurrence

Question

which of the following cannot be solved using masters theorem?

a) T(n) = 2T(n/2) + n/logn

b) T(n) = 2T(n/2) + logn

c)T(n)=T(n/2)+logn

d) non of these

Comments

b is the answer

---

@manvi_agarwal, answer may be wrong

refer the 2nd link which i provided

---

Sir u think by advanced master's theorem we can do all of them.

Am i right??

Answer 1

General form of master's theorem -

T(n)=aT(n/b)+Q(n^k (log^p)n)

where a>=1,b>1,k>=0 and p is real.

according to this all are satisfied so ans is D.

Comments

You are right bro..

But what about this 

https://gateoverflow.in/227814/introduction-to-algorithms

---

Did u find answer to that?

Answer 2

 

Inadmissible equations

The following equations cannot be solved using the master theorem:

• 

  a is not a constant; the number of subproblems should be fixed

• 

  non-polynomial difference between f(n) and  (see below; extended version applies)

• 

    cannot have less than one sub problem

• 

  f(n), which is the combination time, is not positive

• 

  case 3 but regularity violation.

In the second inadmissible example above, the difference between  and  can be expressed with the ratio . It is clear that  for any constant . Therefore, the difference is not polynomial and the basic form of the Master Theorem does not apply. The extended form (case 2b) does apply, giving the solution .

I have completely copied this portion from wikipedia https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms). 

and from the second inadmissible equation, it is clear that the correct answer is A