Quiz on Algorithm Analysis

Which notation is used to describe the upper bound of an algorithm's growth rate?

• Theta Notation

• Big-Oh Notation

• Big-Omega Notation

• Little-Oh Notation

What does 'Worst case complexity' refer to?

• The minimum time an algorithm can take to complete

• The maximum time an algorithm can take to complete

• The best possible scenario for an algorithm

• The average performance of an algorithm

Which of the following is NOT a type of asymptotic notation?

• Linear Notation

• Little-Omega Notation

• Big-Oh Notation

• Tilde Notation

How many passes does an insertion sort algorithm consist of?

• a) N

• b) N-1

• c) N+1

• d) N²

What is the average case running time of an insertion sort algorithm?

• O(N)

• O(NlogN)

• O(logN)

• O(N²)

What is the running time of an insertion sort algorithm if the input is pre-sorted?

• O(N²)

• 
  O(N log N)

• O(N)

• O(M log N)

For the following question, how will the array elements look like after second pass?
34, 8, 64, 51, 32, 21

• 8, 21, 32, 34, 51, 64

• 8, 32, 34, 51, 64, 21

• 
  8, 34, 51, 64, 32, 21

• 
  8, 34, 64, 51, 32, 21

Identify the two types of efficiencies that are important for computer algorithm

• Time and Higher power efficiency

• Higher power efficiency and Computation efficiency

• Computational efficiency and Space efficiency

• Time efficiency and Space efficiency

int fun(int n) {

int count = 0;

for (int i = n; i > 0; i /= 2)

for (int j = 0; j < i; j++)

count += 1;

return count;

}

• O(N^2)

• O(nlogn)

• O(n)

• O(1)

void fun(int n, int arr[])

{

int i = 0, j = 0;

for (; i < n; ++i)

while (j < n && arr[i] < arr[j])

j++;

}

• O(N)

• O(N^2)

• O(nlogn)

• O(N^n)