Description

1. Use the formal definitions of asymptotic notations to determine whetherthe following statements are true or not. (Answers without explanation will not be accepted.)

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.

3. Compare and sort the following functions in terms of their orders of growthby using limit approach.
(a) logn, nlogn, n1.5
(Use Stirling’s formula for 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
(a) What is its basic operation?
(b) How many times is the basic operation executed? (Set up a sumexpressing the number of times the algorithm’s basic operation is executed.)
(c) What is the time complexity of the algorithm? (Derive from the sumexpression 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 sumexpressing the number of times the algorithm’s basic operation is executed.)
(c) What is the time complexity of the algorithm? (Derive from the sumexpression obtained from question (b))
6. Design an algorithm that finds and prints all pairs whose multiplicationyields 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