Big O Notations - Sorting Algorithms

Question 1

Big O for Quicksort

Answer 1

Time
Best: Ω(n log(n))
Average: Θ(n log(n))
Worst: O(n^2)

Space
Worst: Θ(log(n))

Question 2

Big O for Mergesort

Answer 2

Time
Best: Ω(n log(n))
Average: Θ(n log(n))
Worst: Θ(n log(n))

Space
Worst: O(n)

Question 3

Big O for Timsort

Answer 3

Time
Best: Ω(n)
Average: Θ(n log(n))
Worst: 0(n log(n))

Space
Worst: O(n)

Question 4

Big O for Heapsort

Answer 4

Time
Best: Ω(n log(n))
Average: Θ(n log(n))
Worst: O(n log(n))

Space
Worst: O(1)

Question 5

Big O for Bubble Sort

Answer 5

Time
Best: Ω(n)
Average: O(n^2)
Worst: O(n^2)

Space
Worst: O(1)

Question 6

Big O for Insertion Sort

Answer 6

Time
Best: Ω(n)
Average: O(n^2)
Worst: O(n^2)

Space
Worst: O(1)

Question 7

Big O for Selection Sort

Answer 7

Time
Best: Ω(n^2)
Average: O(n^2)
Worst: O(n^2)

Space
Worst: O(1)

Question 8

Big O for Tree Sort

Answer 8

Time
Best: Ω(n log(n))
Average: Θ(n log(n))
Worst: O(n^2)

Space
Worst: O(n)

Question 9

Big O for Shell Sort

Answer 9

Time
Best: Ω(n log(n))
Average: Θ(n(log(n))^2
Worst: Θ(n(log(n))^2

Space
Worst: O(1)

Question 10

Big O for Bucket Sort

Answer 10

Time
Best: Ω(n+k)
Average: O(nk)
Worst: O(n^2)

Space
Worst: O(n)

Question 11

Big O for Radix Sort

Answer 11

Time
Best: Ω(nk)
Average: Θ(nk)
Worst: O(nk)

Space
Worst: O(n+k)

Question 12

Big O for Counting Sort

Answer 12

Time
Best: Ω(n+k)
Average: Θ(n+k)
Worst: O(n+k)

Space
Worst: O(k)

Question 13

Big O for Cubesort

Answer 13

Time
Best: Ω(n)
Average: Θ(n log(n))
Worst: Θ(n log(n))

Space
Worst: O(n)