Time Complexity Flashcards
1
Q
What is amortized time complexity?
A
Cost averaged over multiple operations.
2
Q
What types of problems have O(log n) and O(n log n)?
A
O(log n) is common in divide-and-conquer (e.g., binary search), O(n log n) appears in sorting (e.g., Merge Sort, Quick Sort).
3
Q
What is Big O Notation?
A
Describes worst-case runtime growth rate.
4
Q
What is quadratic growth and when is it often seen?
A
O(n²), if an algorithm has nested loops and the inner loop shrinks or grows based on the outer loop.
5
Q
What is the time complexity of finding all permutations? and why?
A
O(n!) because there are n! possible permutations.
