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