Missed a few classes and need help with this assignment. For each of the followi
ID: 3829559 • Letter: M
Question
Missed a few classes and need help with this assignment.
For each of the following code snippets, find the asymptotic running time (i.e. Theta). Justify your answer using either the substitution method or recursion trees. For each of these, let T(0) = T(1) = 1. (a) T(n) = T(n/2) + 5. (b) T(n) = T(n/2) + n. (c) T(n) = 2 middot T(n/2) + 10. (d) T(n) = 3 middot T(n/3) + n. (e) T(n) = 5 middot T(n/2). (f) T(n) = T(n - 1) + 1 (g) T(n) = T(n - 2) + 3n. (h) T(n) = T(n - 1) + n^2. Consider the array A = [8, 3, 4, 5, 2, 1, 0, 9, 7, 6]. (a) Demonstrate how the insertion sort algorithm works, by showing what A looks like each time the while loop terminates. (CLRS page 18 has the algorithm). (b) Demonstrate how the merge sort algorithm works, by showing how the array is split for each recursive call, and how the algorithm then merges the sorted subarrays. (CLRS page 34 has the algorithm). Prove that counting sort is a stable sort, i.e. if A comes before B in the input and A = B, then A comes before B in the output.Explanation / Answer
T(0) = T(1) = 1.
a. T(n) = T(n/2) + 5.
Assume n = 2^k.
T(n) = T(2^k) + 5.
= T(2^(k-1)) + 5^2.
= T(2^(k-2)) + 5^3.
= ...
= T(2^(k-k)) + 5^(k+1) = T(1) + 5^(k+1) = 1 + 5^(log n + 1).
b. T(n) = T(n/2) + n.
Assume n = 2^k.
T(n) = T(2^k) + n.
= T(2^(k-1)) + n^2.
= T(2^(k-2)) + n^3.
= ...
= T(2^(k-k)) + n^(k+1) = T(1) + n^(k+1) = 1 + n^(log n + 1).
c. T(n) = 2 T(n/2) + 10.
Assume n = 2^k.
T(n) = 2 T(2^k) + 10.
= 2^2 T(2^(k-1)) + 10^2.
= 2^3 T(2^(k-2)) + 10^3.
= ...
= 2^(k+1) T(2^(k-k)) + 10^(k+1) = 2^(k+1) T(1) + 5^(k+1) = 2^(log n +1) + 10^(log n + 1).
d. T(n) = 3 T(n/3) + n.
Assum n = 3^k.
T(n) = 3 T(3^k) + n.
= 3^2 T(3^(k-1)) + n^2.
= 3^3 T(3^(k-2)) + n^3.
= ...
= 3^(k+1) T(3^(k-k)) + n^(k+1) = 3^(k+1) T(1) + n^(k+1) = 3^(log n + 1) + n^(log n + 1).