CODEWITHSUNDEEP
algorithmbig-oanalysis
Eli Taylor
Eli Taylor

Reputation: 51

Why Master theorem cannot be applied

Doing an assignment and stuck on a few questions.

  1. T(n) = T(2n/5)+n
  2. T(n) = T(2n/3)+T(n/3)+n
  3. T(n) = T(n−2)+n

Something tells me that on all of them the Master theorem cannot be applied. But why? And what are their upper bounds (big-Oh)?

Upvotes: 0

Views: 10169

Answers (2)

arunk2
arunk2

Reputation: 2416

The master method works only for following type of recurrences.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

For the questions,

1. T(n) = T(2n/5)+n

@templatetypedef has already modified this recurrence equation to fit the master theorem as

T(n) = T(n / (5/2)) + n

I guess you can solve it from here.

2. T(n) = T(2n/3)+T(n/3)+n

Clearly this cannot be solved directly by master theorem. We should try constructing the recursion tree and see. A recursion tree diagrams the tree of recursive calls and the amount of work done at each call. Following is the image taken from here

enter image description here

So, this reduces to O(n * log n)

3. T(n) = T(n−2)+n

Clearly this cannot be solved directly by master theorem. There is a modified formula derived for Subtract-and-Conquer type.

This link might be useful.

For recurrences of form,

T(n) = aT(n-b) + f(n)

where n > 1, a>0, b>0

If f(n) is O(nk) and k>=0, then

  1. If a<1 then T(n) = O(nk)
  2. If a=1 then T(n) = O(nk+1)
  3. if a>1 then T(n) = O(nk * an/b)

I guess you can solve it from here.

Hope it helps!

Upvotes: 6

templatetypedef
templatetypedef

Reputation: 372784

The Master Theorem can be applied to any recurrence of the form

T(n) = aT(n / b) + O(nd)

where a, b, and d are constants. (There are some other formulations, but this above one handles the more common cases). Specifically, this means that

  • the problem size must shrink by a constant factor,
  • the subproblems must all have the same size,
  • there must be a constant number of subproblems, and
  • the additive term must be a polynomial.

These criteria rule out the second recurrence (the subproblems don't have the same sizes) and the third (the problem size must shrink by a constant factor). However, the first recurrence satisfies all four of these criteria. It might help to rewrite the recurrence as

T(n) = T(n / (5/2)) + n.

Based on that, what case of the Master Theorem are you in, and what does the recurrence solve to?

Upvotes: 2

Related Questions