Sorting Time Complexities

Question 1

Quick Sort

Answer 1

• Best Case: O(nlogn)
• Average Case: O(nlogn)
• Worst Case: O(n²) (if the pivot is consistently the smallest or largest)

Question 2

Merge Sort

Answer 2

• Best Case: O(nlogn)
  -Average Case: O(nlogn)
• Worst: O(nlogn)

Question 3

Bubble Sort

Answer 3

• Best: O(n)
• Worst: O(n^2)

Question 4

Insertion Sort

Answer 4

• Best Case: O(n) (when the array is already sorted)
• Worst Case: O(n²) (when the array is in reverse order)

Question 5

Selection Sort

Answer 5

• Best Case: O(n²) (when the array is already sorted)
• Worst Case: O(n²) (when the array is in reverse order)

Question 6

Tree Sort

Answer 6

• Best Case: O(nlogn)
  -Average Case: O(nlogn)
• Worst: O(nlogn)

Question 7

Heap Sort

Answer 7

• Best Case: O(nlogn)
  -Average Case: O(nlogn)
• Worst: O(nlogn)

Question 8

Bucket Sort

Answer 8

• O(n) to place n items into buckets, plus O(n) to concatenate if n > d
• O(d) if n < d. Typically O(n) in practice.

d - amount of empty buckets

Question 9

Radix Sort (MSD)

Answer 9

• O((n + R) · (max. length of key))
• O(n + R) when maximum key length is constant

Question 10

Radix Sort (LSD)

Answer 10

• O((n + R) · (max. length of key)),
• O(n + R) when key length is fixed.