CLICK HERE TO DOWNLOAD THIS ANSWER INSTANTLY $9.99 Only
1. Use the formal definitions of Big O (not the Limit Rule) to establish the following statements. In each case you need to specific values of the constants (e.g., c1, c2, n0) you used to satisfy the conditions, and show how you arrived at these values.
(a) 4n2 + 4n + 12 = O(n2 − 4n + 8)
(b) 2n3 − 3n2 + 17n = Θ(n3).
(c) n2 + 10n lg2 n = O(n2). (Hint: Find n0 such that lg2 n ≤ n, for
all n ≥n0.)
2. Rank the following functions in increasing order of asymptotic growth rate. For functions that are asymptotically equivalent, group them together
f1(n)= 500n^3
f2(n) = 17n+(2/n^2)
f3(n) = 7n lg lg n
f4(n) = 20n lg^3 n + 5n^2
f5(n) = 4sqrt n + 3lg(n^2)
f6(n) = 2^sqrt n
f7(n)= 2^(3lg n)
f8(n) = 5lg^2 n + 10 lg n
f9(n) = 20 lg(n^2)
f10(n) = 4log3 n
3. Selection Sort can be thought of as a recursive algorithm as follows: Find the largest element and put it at the end of the list (to be sorted). Recursively sort the remaining
elements. That is, F(n) = F(n-1) + some operations.
a. Write down the recursive version of Selection Sort in psuedocode.
b. Derive a recurrence for the exact number of comparisons that your algorithm uses.
c. Use the iteration method to solve the recurrence.
Simplify as much as possible.
