Time & Space Complexity Flashcards
1
Q
What is the time complexity of sorting an array with Quick Sort?
A
Average O(n log n), Worst O(n²).
2
Q
What is the best-case and worst-case time complexity of Merge Sort?
A
Average O(n log n), Worst O(n²).
3
Q
What is the time complexity of inserting an element into a balanced BST?
A
O(n log n) for best, worst, and average case.
4
Q
What is the worst-case time complexity of searching in a hash table?
A
O(n) (if all keys collide).
5
Q
What is amortized time complexity?
A
Cost averaged over multiple operations.
6
Q
What is the difference between O(log n) and O(n log n)?
A
Logarithmic (e.g., binary search) vs. log-linear (e.g., sorting).
7
Q
What is Big O Notation
A
Describes worst-case runtime growth rate.
