# 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?

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!
(09-14-2017, 06:14 PM)SSinischo Wrote: [ -> ]Can you explain how to solve this with substitution?

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!

You should be careful with making a substitution with the same variable name.

T(n) = T(n-1) + O(1)
Let n = lg(m)
T(lg(m)) = T(lg(m) - lg(2)) + O(1) = T(lg(m/2)) + O(1)
Let S(m) = T(lg(m))
S(m) = S(m/2) + O(1)
m^log_b(a) = m^log_2(1) = m^0 = Θ(1) -> Case 2 -> S(m) = Θ(m^0 * lg(m)) = Θ(lg(m)) = T(n) = Θ(n)

Also note that, although it didn't matter in this particular example, the constant hidden in O(f(n)) can sometimes matter because across substitutions the constant can become an exponent.