[ACE] Recurrence Relation
Recurrence Relation Acknowledgement The following content is summarized by G52ACE class and MIT open source course(Introduction to Algorithms). Main Body We don’t care the official definition of recurrence relation, but we need to know: Suppose that the runtime of a program is T(n), then a recurrence relation will express T(n) in terms of its values at other (smaller) values of n. Example: Suppose the runtime of merge-sort of an array of n integers is T(n). Then T(n) = 2 T(n/2) + b + a n: • “2 T(n/2)” is due to having to sort the two sub-arrays each of size n/2 • “b” is the cost of doing the split • “a n” is the cost of doing the merge (and any copying to/from the workspace, etc.) Also, what is our base case? ===> T(1) = 1 Thus, how can we solve this recurrence relation? Solving Recurrence using induction(introduced by G52ACE course) General pattern 1. Starting from the base case, use the recurrence to work out many cases, by directly substituting and working u...