Array Sorting Algorithms Time and Space Complexity

Question 1

What is the best, average, and worst time complexity for quicksort? What is the worst space complexity?

Answer 1

Best = Ω(n log n)
Average = Θ(n log n)
Worst = O(n^2)
Space = O(log n)

Question 2

What is the best, average, and worst time complexity for mergesort? What is the worst space complexity?

Answer 2

Best = Ω(n log n)
Average = Θ(n log n)
Worst = O(n log n)
Space = O(n)

Question 3

What is the best, average, and worst time complexity for timsort? What is the worst space complexity?

Answer 3

Best = Ω(n)
Average = Θ(n log n)
Worst = O(n log n)
Space = O(n)

Question 4

What is the best, average, and worst time complexity for heapsort? What is the worst space complexity?

Answer 4

Best = Ω(n log n)
Average = Θ(n log n)
Worst = O(n log n)
Space = O(1)

Question 5

What is the best, average, and worst time complexity for bubble sort? What is the worst space complexity?

Answer 5

Best = Ω(n)
Average = Θ(n^2)
Worst = O(n^2)
Space = O(1)

Question 6

What is the best, average, and worst time complexity for insertion sort? What is the worst space complexity?

Answer 6

Best = Ω(n)
Average = Θ(n^2)
Worst = O(n^2)
Space = O(1)

Question 7

What is the best, average, and worst time complexity for selection sort? What is the worst space complexity?

Answer 7

Best = Ω(n^2)
Average = Θ(n^2)
Worst = O(n^2)
Space = O(1)

Question 8

What is the best, average, and worst time complexity for tree sort? What is the worst space complexity?

Answer 8

Best = Ω(n log n)
Average = Θ(n log n)
Worst = O(n^2)
Space = O(n)

Question 9

What is the best, average, and worst time complexity for shell sort? What is the worst space complexity?

Answer 9

Best = Ω(n log n)
Average = Θ(n (log n)^2)
Worst = O(n (log n)^2)
Space = O(1)

Question 10

What is the best, average, and worst time complexity for bucket sort? What is the worst space complexity?

Answer 10

Best = Ω(n + k)
Average = Θ(n + k)
Worst = O(n^2)
Space = O(n)

Question 11

What is the best, average, and worst time complexity for radix sort? What is the worst space complexity?

Answer 11

Best = Ω(nk)
Average = Θ(nk)
Worst = O(n^2)
Space = O(n)

Question 12

What is the best, average, and worst time complexity for counting sort? What is the worst space complexity?

Answer 12

Best = Ω(n + k)
Average = Θ(n + k)
Worst = O(n + k)
Space = O(k)

Question 13

What is the best, average, and worst time complexity for cubesort? What is the worst space complexity?

Answer 13

Best = Ω(n)
Average = Θ(n log n)
Worst = O(n log n)
Space = O(n)