Given the following two functions: • f(n) = 3n^2 + 5 • g(n) = 53n + 9 Use limits to prove or disprove
engineering
Description
1. Given the following two functions: • f(n) = 3n^2 + 5 • g(n) = 53n + 9 Use limits to prove or disprove each of the following: • f ∈ Ω(g) • g ∈ Θ(f) Answer: f(n) = 3n^2 + 5 g(n)= 53n +9 f(g(n) = 3 *(53*n +9)^2 + 5 = 3 *(53*53n^2 +81+952) +5 -equation 1 g(f(n)) = 53 *(3n^2 +5) +9 -equation2 Ω(g)=n 0(f)=n^2 From equation1 and equation 2 it is proved that: f(g(n) != g(f(n)) 2. Rank the following functions from lowest asymptotic order to highest. List any two or more that are of the same order on the same line. • 2^n • n^3 + 5n • log2_n • n^3 + 2^ 2 + 1 • 3^n • n^2 + 5n + 10 • n log_2 n • 10n + 7 • √n Answer: (Log_3 n = log_2 n) √n 10n + 7 n log_2 n n^ 2 + 5n + 10 (n^ 3 + 2n^ 2 + 1 = n^ 3 + 5n) 2^n 3^n 3. Consider the following functions for problems 3 and 4 int max(int[] array, int first, int last) { if (first == last) return array[first]; else if (first + 1 == last) return max(array[first], array[last]); else { int mid = (first + last) / 2; return max(max(array, first, mid), max(array, mid + 1, last)); } } int max(int left, int right) { if (left > right) return left; return right; } Write the recurrence equation that e!xpresses the execution time cost for the above algorithm. Draw the recursion tree assuming that n= 8. Answer: T(n) = T(n/2)+T(n/2)+c T(n)=2T(n/2)+c 4. 4. Determine the critical exponent for the recurrence equation in problem 3. Apply the Little Master Theorem to solve that equation. Is this algorithm optimal? Explain. Answer: T(n)=2T(n/2)+c Applying master theorem: a=2 and b=2 , c=0 log_b(a)>c T(n)=O(n)
Instruction Files
451h2_sol (3) (1).docx
937.6 KB
