Description
1. Use the formal definitions of asymptotic notations to determine whether
the following statements are true or not. (Answers without explanation
will not be accepted.)
(a) (2n + n
3
) ∈ O(4n)
(b) √
10n2 + 7n + 3 ∈ Ω(n)
(c) n
2 + n ∈ o(n
2
)
(d) 3 log2
2 n ∈ θ(log2 n
2
)
(e) (n
3 + 1)6 ∈ O(n
3
)
2. Use the formal definition of θ notation to find θ(g(n)) class the following
functions belong to. Give the simplest g(n) possible in your answers.
(a) 2n log (n + 2)2 + (n + 2)2
log n
2
(b) 0.001n
4 + 3n
3 + 1
3. Compare and sort the following functions in terms of their orders of growth
by using limit approach.
(a) log n, nlog n, n1.5
(b) n!, 2
n, n2
(Use Stirling’s formula for n!)
(c) n log n, √
n
(d) n2
n, 3
n
(e) √
n + 10, n3
4. Consider the worst case of the following algorithm.
algorithm1(B[0..n-1,0..n-1])
for i=0 to n-2 do
for j=i+1 to n-1 do
if B[i,j]!=B[j,i]
return false
return true
1
(a) What is its basic operation?
(b) How many times is the basic operation executed? (Set up a sum
expressing the number of times the algorithm’s basic operation is
executed.)
(c) What is the time complexity of the algorithm? (Derive from the sum
expression obtained from question (b))
5. Consider the following algorithm.
algorithm2(A[0..n-1, 0..n-1], B[0..n-1, 0..n-1])
for i=0 to n-1 do
for j=0 to n-1 do
C[i,j]=0.0
for k=0 to n-1 do
C[i,j]=C[i,j]+A[i,k]*B[k,j]
return C
(a) What is its basic operation?
(b) How many times is the basic operation executed? (Set up a sum
expressing the number of times the algorithm’s basic operation is
executed.)
(c) What is the time complexity of the algorithm? (Derive from the sum
expression obtained from question (b))
6. Design an algorithm that finds and prints all pairs whose multiplication
yields the desired number in an unordered array. For example, let the
array be {1,2,3,6,5,4} and let the desired number be 6. Then, our pairs
will be (1,6) and (2,3). Write your algorithm as pseudo-code, and find the
time complexity of the algorithm.
Notes:
• Submissions must be handwritten and readable.
• The homework must be done individually. No collaboration is allowed.
2
