Time Complexity

Question 1

What is amortized time complexity?

Answer 1

Cost averaged over multiple operations.

Question 2

What types of problems have O(log n) and O(n log n)?

Answer 2

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).

Question 3

What is Big O Notation?

Answer 3

Describes worst-case runtime growth rate.

Question 4

What is quadratic growth and when is it often seen?

Answer 4

O(n²), if an algorithm has nested loops and the inner loop shrinks or grows based on the outer loop.

Question 5

What is the time complexity of finding all permutations? and why?

Answer 5

O(n!) because there are n! possible permutations.