Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revision | |
courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 16:17] – [Substituting into the Mergesort Recurrence] mugabej | courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 22:23] (current) – mugabej |
---|
\\ | \\ |
** An Approach Using Partial Substitution**:\\ | ** An Approach Using Partial Substitution**:\\ |
| \\ |
| With this approach: |
| >>>>>>>>>>>>>>> Guess the overall form of the solution without pinning down the exact values of all the constants and other parameters.\\ |
| >>>>>>>>>>>>>>> Suppose we believe that T(n) = O(nlogn) but we're not sure of the constant inside the T(.) notation. So,\\ |
| >>>>>>>>>>>>>>> T(n)≤ kn log<sub>b</sub>nfor some constant k and base b that we solve for.\\ |
| >>>>>>>>>>>>>>> We try to use the induction as follows:\\ |
| >>>>>>>>>>>>>>> T(n)≤ 2T(n/2) + cn ≤ 2k(n/2) log<sub>b</sub>(n/2) + cn\\ |
| >>>>>>>>>>>>>>> Let's now choose 2 as our base since it can help us simplify our expression.So,\\ |
| >>>>>>>>>>>>>>> T(n) ≤ 2k(n/2)log<sub>2</sub>(n/2) + cn\\ |
| >>>>>>>>>>>>>>>>>>>>>>>>>> = 2k(n/2)[(log<sub>2</sub>n)-1] + cn\\ |
| >>>>>>>>>>>>>>>>>>>>>>>>>> = kn[(log<sub>2</sub>n)-1] + cn\\ |
| >>>>>>>>>>>>>>>>>>>>>>>>>> = (knlog<sub>2</sub>n) -kn + cn\\ |
| >>>>>>>>>>>>>>> Finally we ask ourselves if there is a choice of k that will make this expression be bounded by knlog<sub>2</sub>n\\ |
| >>>>>>>>>>>>>>> From the expression,it's obvious that we just need to choose a k that is at least as large as c, which gives us:\\ |
| >>>>>>>>>>>>>>> T(n) ≤ (knlog<sub>2</sub>n) -kn + cn ≤ knlog<sub>2</sub>n\\ |
| >>>>>>>>>>>>>>> Thus our proof is completed.\\ |
| \\ |
| As useful as it is, our this section was really short and straightforward. I give a 9/10. |
| |
| |
| |