Quote:54. The recurrence: T(n) = T(n-1) + O(1) reduces to:

- O((log n)*(log n))

- O(n)

- O(log n)

- 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)

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!

(09-14-2017, 06:14 PM)SSinischo Wrote: [ -> ]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!

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.