Homework 1 Solution

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.)

1. 1. (2ⁿ + n³) ∈ O(4ⁿ)

√

1. 2. 10n² + 7n + 3 ∈ Ω(n)

   3. n² + n ∈ o(n²)

1. 4. 3 log²₂ n ∈ θ(log₂ n²)

1. 5. (n³ + 1)⁶ ∈ O(n³)

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.

1. 1. 2n log (n + 2)² + (n + 2)² log ⁿ₂

   2. 0.001n⁴ + 3n³ + 1

3. Compare and sort the following functions in terms of their orders of growth by using limit approach.

1. 1. log n, n^{log n}, n^1.5

   2. n!, 2ⁿ, n² (Use Stirling’s formula for n!)

√

(c) n log n, n

1. 4. n2ⁿ, 3ⁿ

√

1. 4. n + 10, n³

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. 1. What is its basic operation?

1. 2. How many times is the basic operation executed? (Set up a sum expressing the number of times the algorithm’s basic operation is executed.)

1. 3. 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

1. 1. What is its basic operation?

1. 2. How many times is the basic operation executed? (Set up a sum expressing the number of times the algorithm’s basic operation is executed.)

1. 3. 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