CS Interview Questions Flashcards
Time/Space (best/avg/worst) Complexity Merge Sort
Time: Best: O(n log(n)) Avg: O(n log(n)) Worst: O(n log(n)) Space: O(n)
Time/Space (best/avg/worst) Complexity Quick Sort
Time:
Best: O(n log(n))
Avg: O(n log(n))
Worst: O(n^2)
Space:
O(log(n))
Time/Space (best/avg/worst) Complexity Time Sort
Time:
Best: Ω(n)
Avg: O(n log(n))
Worst: O(n log(n))
Space:
O(n)
Time/Space (best/avg/worst) Complexity Heap Sort
Time:
Best: Ω(n log(n))
Avg: O(n log(n))
Worst: O(n log(n))
Space:
O(1)
Time/Space (best/avg/worst) Complexity Bubble Sort
Time:
Best: Ω(n)
Avg: O(n^2)
Worst: O(n^2)
Space:
O(1)
Time/Space (best/avg/worst) Complexity Insertion Sort
Time:
Best: Ω(n)
Avg: O(n^2)
Worst: O(n^2)
Space:
O(1)
Time/Space (best/avg/worst) Complexity Selection Sort
Time:
Best: Ω(n^2)
Avg: O(n^2)
Worst: O(n^2)
Space:
O(1)
Time/Space (best/avg/worst) Complexity Tree Sort
Time:
Best: Ω(n log(n))
Avg: Θ(n log(n))
Worst: O(n^2)
Space:
O(n)
Time/Space (best/avg/worst) Complexity Shell Sort
Time:
Best: Ω(n log(n))
Avg: Θ(n(log(n))^2)
Worst: O(n(log(n))^2)
Space:
O(1)
Time/Space (best/avg/worst) Complexity Bucket Sort
Time:
Best: Ω(n+k)
Avg: Θ(n + k)
Worst: O(n^2)
Space:
O(n)
Time/Space (best/avg/worst) Complexity Radix Sort
Time:
Best: Ω(nk)
Avg: Θ(nk)
Worst: O(nk)
Space:
O(n+k)
Time/Space (best/avg/worst) Complexity Counting Sort
Time:
Best: Ω(n+k)
Avg: Θ(n+k)
Worst: O(n+k)
Space:
O(k)
Time/Space (best/avg/worst) Complexity Cube Sort
Time:
Best: Ω(n)
Avg: Θ(n log(n))
Worst: O(n log(n))
Space:
O(n)