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 8n3 logn + 14n2 = Θ(n3 logn).
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).
2
n2 , n!, ( 3 )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.
4 A problem on graph: exercise 3.7
Do Exercise 3.7 on page 108 of your book. Note: we will not cover Chapter 3 during week 2. However, this problem only needs basic knowledge of graphs (e.g. when a graph is connected), which I assume you have learned in previous courses.
