IKM Data Structures and Algorithms 2

Question 1

What is the worst-case time complexity of quicksort when the first element is always chosen as the pivot and the input is already sorted?

Accepted Answer

O(n^2)

Answer

A sorted input with a first-element pivot creates maximally unbalanced partitions of size n-1 and 0, giving O(n^2).

Question 2

Which of the following sorting algorithms is stable in its standard implementation?

Accepted Answer

Merge sort

Answer

Standard merge sort preserves the relative order of equal keys by taking from the left half first on ties.

Question 3

What is the lower bound on the worst-case number of comparisons for any comparison-based sorting algorithm?

Accepted Answer

Ω(n log n)

Answer

A decision tree must have at least n! leaves, so its height is at least log2(n!) = Ω(n log n).

Question 4

What is the time complexity of counting sort for n integers in the range 0 to k?

Accepted Answer

O(n + k)

Answer

Counting sort makes one pass over the n inputs and one pass over the k-sized count array.

Question 5

What is the best-case time complexity of insertion sort?

Accepted Answer

O(n)

Answer

On an already sorted array, each element needs only one comparison, so the total work is linear.

IKM - International Knowledge Measurement Practice Test