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