Complexity Analysis

28 / 30
1 min read
1

Complexity Analysis

Big O notation describes how an algorithm's runtime or memory usage grows relative to its input size n.

Common Classes

O(1) - — constant time, independent of input size.
O(log n) - — divides the problem in half each step (binary search).
O(n) - — linear, one pass over the input.
O(n log n) - — efficient sorting algorithms.
O(n²) - — nested loops over the input.
O(2^n) - — exponential; avoid for large inputs.

Best, Average, Worst Case

Best case - : the minimum time for any input of size n.
Average case - : expected time over typical inputs.
Worst case - : maximum time, often what interviews ask for.

Space Complexity

Count extra memory used relative to input size. In-place algorithms use O(1) extra space; recursion and memoization use more.

Comprehension check

Answer all 3 questions correctly to unlock Submit.

1What is the time complexity of binary search on a sorted array?

2Which case is usually reported when asked for Big O complexity?

3An algorithm uses one extra hash map of size n. What is its space complexity?