Quick Guide: Big-O Notation

Big-O notation is our shorthand for how an algorithm’s runtime (or memory use) grows as input size increases. Think of it as a way to talk about "the worst that could happen," without getting down in machine-specific details.

O(1) – Constant time Your algorithm takes the same amount of time no matter how big the input is. Example: Accessing array[5].
O(log n) – Logarithmic time Cutting the problem in half (or any fixed fraction) each step. Example: Binary search on a sorted list.
O(n) – Linear time You do one unit of work per element. Example: Scanning an array to find its maximum.
O(n log n) – Linearithmic time Common for efficient sorts (like quicksort or mergesort). Example: Sorting then scanning.
O(n²), O(n³), … – Polynomial time Nested loops—each adds another factor of n. Example: Checking all pairs = O(n²).
O(2ⁿ), O(n!) – Exponential or factorial time These grow super-fast and become impractical very quickly. Example: Brute-forcing all subsets.

PreviousLeet Code NextProblem 01 - Two Sum

Last updated 1 month ago

Quick Guide: Big-O Notation

O(1) – Constant time Your algorithm takes the same amount of time no matter how big the input is. Example: Accessing array[5].
O(log n) – Logarithmic time Cutting the problem in half (or any fixed fraction) each step. Example: Binary search on a sorted list.
O(n) – Linear time You do one unit of work per element. Example: Scanning an array to find its maximum.
O(n log n) – Linearithmic time Common for efficient sorts (like quicksort or mergesort). Example: Sorting then scanning.
O(n²), O(n³), … – Polynomial time Nested loops—each adds another factor of n. Example: Checking all pairs = O(n²).
O(2ⁿ), O(n!) – Exponential or factorial time These grow super-fast and become impractical very quickly. Example: Brute-forcing all subsets.

PreviousLeet Code NextProblem 01 - Two Sum

Last updated 1 month ago