Need help with problems 1-4: Answer the following by using the definitions for a

Question

Need help with problems 1-4:

Answer the following by using the definitions for asymptotic notations: Prove that 10 = O(n). Is 2n = (2n + 1)? Either prove or explain your answer. Express the function f(n) = n3/100 - 10n2 + n + 3, in terms of -notation. No need for any proof. Just state (?). Order the following set of functions by their growth rates: N, , N1.5, N2, N log N, N log log N, N log2N, N log(N2), 2/N, 2N, 2N/2 , 37, N2 log N, N3. If there are functions that grow at the same rate, indicate them inside braces. There is no need to show proofs or give an explanation. State TRUE or FALSE for the following assertions. If FALSE give a counterexample as well.

Explanation / Answer

3.) 37 , 2/N , sqrt(N) , N , N log logN ,( N logN , Nlog(N^2) ) , N log^2 N , N^2logN, N^1.5 , N^2 , N^3 , 2^N/2 , 2^N 1.) i.)10 sqrt(N) = O(sqrt(N)) = O(N) ii.) theta notation is for best case situation. 2^n bestcase is theta(2^n) itself.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.