The Beastie Forums
#54 (Reducing Recurrence) - Printable Version

+- The Beastie Forums (http://beastie.cs.ua.edu/mybb)
+-- Forum: Programming Languages (http://beastie.cs.ua.edu/mybb/forumdisplay.php?fid=14)
+--- Forum: Exam 1 (http://beastie.cs.ua.edu/mybb/forumdisplay.php?fid=22)
+--- Thread: #54 (Reducing Recurrence) (/showthread.php?tid=105)



#54 (Reducing Recurrence) - davidmccoy - 09-03-2017

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?


RE: #54 (Reducing Recurrence) - lusth - 09-03-2017

Common sense. Or you can write out the open form and use math to find the closed form.


RE: #54 (Reducing Recurrence) - etberryhill - 09-10-2017

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)


RE: #54 (Reducing Recurrence) - lusth - 09-12-2017

^ very good


RE: #54 (Reducing Recurrence) - SSinischo - 09-14-2017

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!


RE: #54 (Reducing Recurrence) - james_h - 10-03-2017

(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.