1 Asymptotic Notations For this problem, you need to base your answer on the definitions of the asymptotic notations (not the common sense rules). 1. Show 8n3logn + 14n2 = Θ(n3logn). 2. If f(n) = O(g(n)), can we conclude 2f(n) = O(2g(n))? Justify your answer. 3. Prove for any integer constant a and real constant b, (n + b)a = Θ(na). In fact, this holds even when a is a real constant, but you do not have to prove it. 2 Asymptotic order The following functions are selected from problem 3-3(a) on page 61 of your textbook (p.58 if you use the 2nd edition). Order these functions asymptotically as explained in the textbook. You do not need to give proof, but you may want to work out yourself for self-study. Note that lgn means log2(n). n2, n!, ( 3 2)n, n3, lg2n, n · 2n, lnn, 1, 2lgn, en, 2n, nlgn, n. 3 Sum of two numbers You are given an array A[1 : : : n] of arbitrary integers and another integer u. The problem is to check if the array A has two elements x and y such that x + y = u. Present an algorithm to solve this problem. What is the run time of your algorithm? Note: you should try to design an algorithm that is more efficient than the simple brute-force algorithm.
