Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision |
| courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 15:49] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 16:17] – [Substituting into the Mergesort Recurrence] mugabej |
|---|
| \\ | \\ |
| ** Identifying the pattern **:\\ | ** Identifying the pattern **:\\ |
| | \\ |
| | >>>>>>>>>>>>>>> At level j of the recursion, the number of subproblems has doubled j time\\ |
| | >>>>>>>>>>>>>>> So, there are now a total of 2^j subproblems.\\ |
| | >>>>>>>>>>>>>>> Each subproblem has in turn decreased its size by a factor of two j times\\ |
| | >>>>>>>>>>>>>>> So,each subproblem has size n/2^j and takes time at most cn/2^j\\ |
| | >>>>>>>>>>>>>>> Thus level j costs us at most 2^j*(cn/2^j) = cn \\ |
| | \\ |
| | ** Summing over all levels of recursion **:\\ |
| | \\ |
| | >>>>>>>>>>>>>>> We know that cn is the upper bound and applies to the total amount of work performed at each level.\\ |
| | >>>>>>>>>>>>>>> The number of times the input must be halved to reduce its size from n to 2 is log<sub>2</sub>n\\ |
| | >>>>>>>>>>>>>>> Thus, after summing the cn work over all logn levels of recursion, we get a total running time of O(nlogn).\\ |
| | >>>>>>>>>>>>>>> So in brief, any function T(.) for which T(n) ≤ 2T(n/2) + cn is bounded by O(nlogn) when n>1.\\ |
| \\ | \\ |
| | |
| | ==== Substituting into the Mergesort Recurrence ==== |
| | |
| | |
| | >>>>>>>>>>>>>>> Let's suppose we think that T(n) ≤ cn log<sub>2</sub>n for all n ≥ 2 and we want to check whether it's true.\\ |
| | >>>>>>>>>>>>>>> The above claims holds for n=2 since cn log<sub>2</sub>n = 2c and we know by the recurrence relation that T(2) ≤ c\\ |
| | >>>>>>>>>>>>>>> Now, we assume by induction that T(m)≤ cmlog<sub>2</sub>m for all m < n, and we want to make prove this for T(n).\\ |
| | >>>>>>>>>>>>>>> To do this, we just compute after appropriate substitutions:\\ |
| | >>>>>>>>>>>>>>> T(n) ≤ 2T(n/2) + cn\\ |
| | >>>>>>>>>>>>>>>>>>>>>> ≤ (2cn/2) log<sub>2</sub>(n/2) + cn\\ |
| | >>>>>>>>>>>>>>>>>>>>>> = cn[(log<sub>2</sub>n)-1)] + cn\\ |
| | >>>>>>>>>>>>>>>>>>>>>> = (cn log<sub>2</sub>n) - cn + cn\\ |
| | >>>>>>>>>>>>>>>>>>>>>> = cn log<sub>2</sub>n\\ |
| | >>>>>>>>>>>>>>> This argument establishes the bound T(n) we want, assuming it holds for smaller values m<n, and thus completes our induction proof.\\ |
| | \\ |
| | ** An Approach Using Partial Substitution**:\\ |
| |
