Rank the following functions from lowest asymptotic order to highest. List any t
ID: 3804176 • Letter: R
Question
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 log_2 n n^3 + 2n^2 + 1 3^n log_3 n n^2 + 5n + 10 n log_2n 10n + 7 Squareroot n 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 + = = 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 expresses the execution time cost for the above algorithm. Draw the recursion tree assuming that n = 8. 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.Explanation / Answer
2)
log2n ----- O(log2n)
log3n ------ O(log3n)
sqrt(n) ---- O(sqrt(n))
n log2n ---- O(n)
10n+7 ------ O(n)
n^2+5n+10 -- O(n^2)
n^3+2n^2+1 - O(n^3)
n^3+5n ----- O(n^3)
2^n ----- O(2^n)
3^n -------- O(3^n)
3)
Getting recurrence relation..
this is for max(int left, int right) ..
T(1) = 0
T(n) = T(n-1)+1, n>1
recurrence will be...
T(n) = 1+1+...1(n-1)
==> T(n) = n-1
second function max(int[] array, int first, int last)
T(1) = 0
T(n) = 2.T(n/2)+n, n>=2
4)
T(1) = 0
T(n) = 2.T(n/2)+n, n>=2
==> so complexity will be O(n.logn)
This algorithm is optimal since it need to take all elements to check.. after some iterations it will avoid some iterations.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.