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)

451h2_sol (3) (1).docx

937.6 KB

Get Higher Grades Now

Tutors Online

Get Free Quote!

369 Experts Online