Quiz 1 - Asymptotic Notations and Correctness of Algorithms

Question 1

Is the following a property that holds for all non-decreasing positive functions f and g?

If f(n) = O(n^2) for c=1 and n0=0 and

g(n) = Theta(n^2) for n0=0 and c1 =1 and c2=1

then f(n) = O(g(n)).

T/F

Answer 1

True

Question 2

Rank the following functions by increasing order of growth:

log( n! ), 10000n2, log(n3), 2n, n2log(n)

Answer 2

log(n3), log( n! ), 10000n^2, n^2log(n), 2^n

Question 3

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

A(n) = Theta(W(n))

A(n) = Omega(W(n))

A(n) = O(W(n))

Answer 3

A(n) = O(W(n))

Question 4

Which of the following can be used to compare two algorithms?

• implementations of the two algorithms
• growth rates of the two algorithms
• number of input parameters required for two algorithms
• computers on which programs which implement the two algorithms are run

Answer 4

• growth rates of the two algorithms

Question 5

If you are given different versions of the same algorithm with the following complexity classes, which one would you select?
* Logarithmic
* Linear
* Polynomial
* Quadratic

Answer 5

• Logarithmic

Question 6

When we say algorithm A is asymptotically more efficient than B, what does that imply?
* A will always be a better choice for large inputs
* A will always be a better choice for small inputs
* B will always be a better choice for all inputs
* B will always be a better choice for small inputs

Answer 6

• A will always be a better choice for large inputs

Question 7

Consider the following algorithm

1 Bubble-sort(a)
2 for i = a.length() to 1
3 for j = 1 to i-1
4 if a[j]>a[j+1]
5 swap(a[j],a[j+1]);
6 end if
What is its basic operation (write the line number of code which would define the execution time of the code)?

Answer 7

4

Question 8

What is the basic operation (that which is executed maximum number of times) in the following code?

reverse(a):
for i = 1 to len(a)-1
x = a[i]
for j = i downto 1
a[j] = a[j-1]
a[0] = x

Answer 8

a[j] = a[j-1]

Question 9

What is the correct loop invariant for the below code:

for i in range(len(A)): # in pseudo-code for i=0,...,len(A)-1

    answer += A[i]    

return answer

• At the start of iteration i of the loop, the variable answer should contain the sum of the numbers from the subarray A[0:i-1].
• The result of this code will be sum of all the elements of the array.
• The loop stops when i reaches the last element of the array.
• The loop iterates from i ranging from 0 to length of the arra

Answer 9

• At the start of iteration i of the loop, the variable answer should contain the sum of the numbers from the subarray A[0:i-1].

Question 10

Select correct inequality for the asymptotic order of growth of the below function. That is, as the value of n becomes very large what is the relation between the two functions.

n ___ n^2

Answer 10

<