diff options
Diffstat (limited to 'notes.md')
| -rw-r--r-- | notes.md | 26 |
1 files changed, 25 insertions, 1 deletions
@@ -730,7 +730,7 @@ Analysis of merge sort ```plaintext ----------------------- - |3|41|52|26|38|57|9|49| + |3|9|26|38|41|49|52|57| ----------------------- / \ ------------ ------------ @@ -783,3 +783,27 @@ for k = k to r A[k] = R[j] j = j + 1 ``` + +2.3-3: Use mathematical induction to show that when `n` is an exact power of 2, +the solution of the recurrence ... is `T(n) = nlg(n)` + +```plaintext + 2 if n = 2 +T(n) = { 2T(n/2) + n if n = 2**k, for k > 1 +``` + + ??? + +2.3-4: We can express insertion sort as a recursive procedure as follows In +order to sort `A[i..n]`, we recursively sort `A[i..n-1]` and then insert `A[n]` +into the sorted array `A[1..n-1]`. Write a recurrence for the worst-case running +time of this recursive version of insertion sort. + + +2.3-5: Referring back to the searching problem (see Exercise 2.1-3), observe that + if the sequence A is sorted, we can check the midpoint of the sequence + against v and eliminate half of the sequence from further consideration. The + binary search algorithm repeats this procedure, halving the size of the + remaining portion of the sequence each time. Write pseudocode, either + iterative or recursive, for binary search. Argue that the worst case running + time of binary search is O(lg(n)). |