Saved Bookmarks
| 1. |
The solution of the recurrence relation t(m) = t( 3m 4) + 1 is |
|
Answer» We can solve this using substitution method. Claim: T(n) <= c n^2 IH: We ASSUME that claim is true for all values of n < m. INDUCTIVE Step: T(m) = T(m/4) + T(3m/4) + m^2 <= cm^2/16 + c 9 m^2 / 16 + m^2 = cm^2 (1/16 + 9/16 + 1/c) = c m^2 (10/16 + 1/c) <= c m^2 as long as 1/c <= 6/16. So, we can choose a value of c >= 16/6 and the rest of the math holds up. QED. Therefore, by PMI, T(n) <= c n^2, that is, T(n) = O(n^2). Alternative Proof: FOLLOW the same logic, but instead of c, USE a larger constant such as 10. T(n) = 10 n^2/16 + 10 9n^2/16 + n^2. <= 10 n^2 |
|