Page 1 of 1
A. Use the Master's Theorem to design a function (it can do anything you want it to) that has an O(n^1.6...) complexity.
Posted: Mon May 02, 2022 11:41 am
by answerhappygod
- A Use The Master S Theorem To Design A Function It Can Do Anything You Want It To That Has An O N 1 6 Complexity 1 (78.86 KiB) Viewed 47 times
A. Use the Master's Theorem to design a function (it can do anything you want it to) that has an O(n^1.6...) complexity. The first two digits should be 1.6 Note: We usually classify the complexity of our algorithms using common Big O sets such as O(n), O(n^3), O(n log n). However, for this exercise, we will use the Big O set the master's theorem gives. Hint: you may want to use binaryO (from week 3) as a starting point. Explain your thought process. п T(n) = a XT (6) + f(n) a = 1. if O(f(n)) < nlog, a, then O(T(n)) = nlog, a 2. if (f(n)) Inlog, a, then O(T(n)) = nlogo a lg n 3. if O(f(n)) > nlog; a, then (T(n)) = O(f(n)) = a B. Without changing the constant "a" and the "f(n)" you used in the master's theorem equation, use the function you made for the previous subquestion to design a O(n^2.6...) algorithm. Hint: use the function as a blackbox function within another function.