The Beastie Forums

Full Version: #54 (Reducing Recurrence)
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Quote:54. The recurrence: T(n) = T(n-1) + O(1) reduces to:
  1. O((log n)*(log n))
  2. O(n)
  3. O(log n)
  4. O(n log n)
This doesn't fit the form of the MRT, right? I'm pretty sure the answer is O(n) despite that. How should I approach reducing this though?
Common sense. Or you can write out the open form and use math to find the closed form.
Seems to be O(n). Each time you recurse you get 1 sub-problem of size (n - 1) where you perform constant work for every sub-problem. Looks like you get the equation: n sub-problems * constant work = O(n)
^ very good
Can you explain how to solve this with substitution?

Tried my hand at it, but don't think I'm going about this the right way:

T(n) = T(n-1) + O(1)
T(log n) = T(log(n) - log(2)) + O(1)
T(log n) = T(log(n/2)) + O(1)

let S(m) = T(log n) = S(m/2) + O(1)

log base 2 of 1 = 0...? But this can't be case 2 - then I'd get theta(m log m) = theta(2^n * n). Help!