algorithm - Why Master theorem cannot be applied -


doing assignment , stuck on 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 on of them master theorem cannot applied. why? , upper bounds (big-oh)?

the master theorem can applied recurrence of form

t(n) = at(n / b) + o(nd)

where a, b, , d constants. (there other formulations, above 1 handles more common cases). specifically, means that

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

these criteria rule out second recurrence (the subproblems don't have same sizes) , third (the problem size must shrink constant factor). however, first recurrence satisfies 4 of these criteria. might rewrite recurrence as

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

based on that, case of master theorem in, , recurrence solve to?


Comments

Popular posts from this blog

ZeroMQ on Windows, with Qt Creator -

unity3d - Unity SceneManager.LoadScene quits application -

python - Error while using APScheduler: 'NoneType' object has no attribute 'now' -