CS Interview Questions

Question 1

Time/Space (best/avg/worst) Complexity Merge Sort

Answer 1

Time:
Best: O(n log(n))
Avg: O(n log(n))
Worst: O(n log(n))
Space: 
O(n)

Question 2

Time/Space (best/avg/worst) Complexity Quick Sort

Answer 2

Time:
Best: O(n log(n))
Avg: O(n log(n))
Worst: O(n^2)

Space:
O(log(n))

Question 3

Time/Space (best/avg/worst) Complexity Time Sort

Answer 3

Time:
Best: Ω(n)
Avg: O(n log(n))
Worst: O(n log(n))

Space:
O(n)

Question 4

Time/Space (best/avg/worst) Complexity Heap Sort

Answer 4

Time:
Best: Ω(n log(n))
Avg: O(n log(n))
Worst: O(n log(n))

Space:
O(1)

Question 5

Time/Space (best/avg/worst) Complexity Bubble Sort

Answer 5

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

Space:
O(1)

Question 6

Time/Space (best/avg/worst) Complexity Insertion Sort

Answer 6

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

Space:
O(1)

Question 7

Time/Space (best/avg/worst) Complexity Selection Sort

Answer 7

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

Space:
O(1)

Question 8

Time/Space (best/avg/worst) Complexity Tree Sort

Answer 8

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

Space:
O(n)

Question 9

Time/Space (best/avg/worst) Complexity Shell Sort

Answer 9

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

Space:
O(1)

Question 10

Time/Space (best/avg/worst) Complexity Bucket Sort

Answer 10

Time:
Best: Ω(n+k)
Avg: Θ(n + k)
Worst: O(n^2)

Space:
O(n)

Question 11

Time/Space (best/avg/worst) Complexity Radix Sort

Answer 11

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

Space:
O(n+k)

Question 12

Time/Space (best/avg/worst) Complexity Counting Sort

Answer 12

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

Space:
O(k)

Question 13

Time/Space (best/avg/worst) Complexity Cube Sort

Answer 13

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

Space:
O(n)