1. What Is Big O Notation?

Big O notation describes how the time or memory required by an algorithm grows as the input size grows.

It helps answer questions such as:

How well does an algorithm scale?

What happens when the input becomes very large?

Which of two algorithms is more efficient?

How much additional memory does an algorithm require?

Big O usually describes:

Time Complexity: how the amount of work grows.

Space Complexity: how the additional memory usage grows.

For example:

If the array contains N elements, the loop processes N elements. Therefore, time complexity is O(N)

function printNumbers(nums) {
  for (const num of nums) {
    console.log(num);
  }
}

2. What Does `N` Mean?

N represents the size of the input. Its meaning depends on the problem.

Problem	Input Size
Array	`N` = number of elements
String	`N` = number of characters
Linked List	`N` = number of nodes
Tree	`N` = number of nodes
Matrix	`R` rows and `C` columns
Graph	`V` vertices and `E` edges

For example: Here, N = the number of elements in nums.

function findTarget(nums, target) {
  for (const num of nums) {
    if (num === target) return true;
  }
  return false;
}

3. Big O, Big Omega, and Big Theta

There are three main asymptotic notations:

Notation		Meaning	Grow
Big O	`O(f(N))`	Upper bound	grows at most this fast asymptotically.
Big Omega	`Ω(f(N))`	Lower bound	grows at least this fast asymptotically.
Big Theta	`Θ(f(N))`	Tight bound	grows at this rate asymptotically.

These notations describe asymptotic bounds. O(f(N)) is an upper bound, Ω(f(N)) is a lower bound, and Θ(f(N)) is a tight bound. For example, T(N) = 3N + 10 grows linearly, so it is both O(N) and Ω(N), therefore Θ(N).

Upper + Lower at the same growth rate → Tight

In everyday algorithm discussions, Big O is the notation used most often.

4. Best, Average, and Worst Case

An algorithm may require different amounts of work depending on the input. Best, average, and worst case describe which inputs or execution scenarios are being analyzed. They are separate from Big O, Big Omega, and Big Theta. For Linear Search, the best-case time is Θ(1) when the target is first, while the worst-case time is Θ(N) when the target is last or absent. If the target is guaranteed to be present and is equally likely to appear at any position, the average-case time is also Θ(N).

5. Big O Measures Growth, Not Exact Runtime

Big O does not tell us: This algorithm takes exactly 3 milliseconds. Instead, it tells us: How does the amount of work change when the input becomes larger? Consider:

for (let i = 0; i < n; i++) {
  console.log(i);
}

This performs approximately: N operations. Now consider:

for (let i = 0; i < n; i++) {
  console.log(i);
  console.log(i);
  console.log(i);
}

This performs approximately: 3N operations.

The second algorithm does more actual work, but both grow at the same linear rate. Therefore, both are: O(N). Big O focuses on growth, not exact operation count.

6. How Fast Do the Complexities Grow?

The differences between complexity classes become much larger as N grows. At N = 1,000, an O(log N) algorithm may require only about 10 growth units, an O(N) algorithm about 1,000, and an O(N²) algorithm about 1,000,000. This is why Big O becomes especially important for large inputs.

Algorithms with slower-growing complexity usually scale much better as the input becomes large.

`N`	`log₂ N`	`N log₂ N`	`N²`	`2ᴺ`
10	~3	~33	100	1,024
100	~7	~664	10,000	~1.27 × 10³⁰
1,000	~10	~9,966	1,000,000	Enormous

7. Rules for Calculating Big O

There are four main rules.

Ignore Constants: Constant multipliers do not change the growth class: O(5N) → O(N), O(100N²) → O(N²)

Only keep the Dominant Term: Keep the term that grows fastest:
Big O focuses on how the algorithm grows for very large N. As N increases, N³ grows much faster than N² and N, so the smaller terms become insignificant compared with it.

Expression Simplified

N + 100 O(N)

5N + 20 O(N)

N² + N O(N²)

N³ + N² + N O(N³)

Expression	Simplified
`N + 100`	`O(N)`
`5N + 20`	`O(N)`
`N² + N`	`O(N²)`
`N³ + N² + N`	`O(N³)`

Sequential Work Adds: Two consecutive O(N) operations give: O(N + N) → O(2N) → O(N). In 2N, the 2 is just a constant multiplier. It makes the algorithm do twice as much work, but the growth is still linear. If two operations depend on independent input sizes, keep both variables. For example, processing N elements and then M elements is O(N + M), not O(N).

function dummy() {
  for (let i = 0; i < n; i++) {...}
  for (let i = 0; i < n; i++) {...}
}

Nested Work Usually Multiplies: Two full nested loops over N give: O(N × N) → O(N²) In N², the 2 is an exponent on N. It changes the growth rate itself from linear to quadratic. If nested loops depend on different input sizes, the complexity may be O(N × M) rather than O(N²).

function dummy() {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {...}
  }
}

But always count the actual iterations. A loop nested inside another loop but running only 10 times still produces O(10N) → O(N).

8. Amortized Complexity

Sometimes an operation is occasionally expensive but inexpensive on average across a sequence of operations. This is called amortized complexity. Consider appending to a dynamic array. Most appends are O(1). Occasionally the array becomes full and must:

Allocate a larger array.

Copy existing elements.

Insert the new element.

That individual operation may be O(N). But resizing happens infrequently. When the cost is spread across many appends: O(1) amortized time per append.

Amortized analysis is different from average-case probability. It analyzes the total cost of a sequence of operations.

9. How to Analyze an Algorithm

10. Time Complexity vs Space Complexity

Time complexity describes how the amount of work grows with the input size. If an algorithm visits all N elements once, such as for (const num of nums), its time complexity is O(N).

Space complexity describes how memory usage grows with the input size. Creating a new array containing N elements requires O(N) auxiliary space, while using only a few variables requires O(1) auxiliary space.

Auxiliary space means additional memory used by the algorithm, excluding the original input.

function sumArray1(nums) {
  let sum = 0;
  for (const num of nums) {
    sum += num;
  }
  return sum;
}

function sumArray2(nums) {
  const result = [];
  for (const num of nums) {
    result.push(num * 2);
  }
  return result;
}

Function	Algorithm Behavior	Time	Auxiliary Space
`sumArray1`	Traverse an array (visited every element once) and calculate a sum	`O(N)`	`O(1)`
`sumArray2`	Traverse an array and create a copy `result` array of size `N`	`O(N)`	`O(N)`

11. Time-Space Tradeoffs

Suppose we want to detect duplicates. Without extra memory, comparing every pair costs O(N²) time and O(1) extra space, while using a Hash Set can reduce average time to O(N) but requires O(N) extra space.

In many applications, using reasonable additional space to achieve a significantly better time complexity is worthwhile, but the best choice depends on memory limits and problem requirements.

12. The Main Big O Complexities

For large N, the general growth order is:

O(1) < O(α(N)) < O(log N) < O(√N) < O(N) < O(N log N) < O(N²) < O(N³) < O(2ᴺ) < O(N!)

Complexity	Name	Pattern / Intuition	Common Example
`O(1)`	Constant	Direct access; work does not grow with input size	Array index access
`O(α(N))` amortized	Inverse Ackermann	Grows extremely slowly; almost constant in practice	Optimized Union-Find
`O(log N)`	Logarithmic	Repeatedly reduce the problem by a constant factor, often by half	Binary Search
`O(√N)`	Square Root	Process only up to the square root of the input	Optimized primality check
`O(N)`	Linear	Visit each element once or a constant number of times	Array traversal
`O(N log N)`	Linearithmic	Process about `N` elements across about `log N` levels	Merge Sort
`O(N²)`	Quadratic	Process every pair or use two full nested `N` loops	Pairwise comparison
`O(N³)`	Cubic	Process combinations across three full `N` dimensions	Three full nested loops
`O(2ᴺ)`	Exponential	Each element creates two possible choices	Generate all subsets
`O(N!)`	Factorial	Explore every possible ordering of the elements	Generate all permutations

`O(1)` Constant Time

O(1) means the amount of work stays approximately the same regardless of how large the input becomes. The algorithm performs a fixed number of operations that does not depend on N. For example, accessing nums[5] does not require checking the elements before it, so an array with 10 elements and an array with 1 million elements require essentially the same amount of work for that access. O(1) does not mean exactly one operation; it means the number of operations does not grow with the input size.

function getElement(nums, index) {
  return nums[index];
}

`O(α(N))` Inverse Ackermann Time

O(α(N)) means the amount of work grows with the input, but at an extraordinarily slow rate. The inverse Ackermann function α(N) increases so slowly that for any realistic computer input it remains a very small number, usually no more than about 5 depending on the mathematical definition used. For this reason, O(α(N)) behaves almost like O(1) in practice, although it is not mathematically constant. A common example is optimized Union-Find, where path compression combined with union by rank or size gives O(α(N)) amortized time per operation over a sequence of operations.

`O(log N)` Logarithmic Time

O(log N) means the amount of work grows very slowly because the algorithm significantly reduces the remaining problem at each step. A common pattern is repeatedly dividing the problem in half, such as in Binary Search. If the input doubles, the algorithm usually needs only about one additional step. For example, searching 1,000,000 sorted elements with Binary Search requires only about 20 comparisons in the worst case, which makes logarithmic algorithms highly scalable.

`O(√N)` Square-Root Time

O(√N) means the number of operations grows roughly with the square root of the input size rather than with the entire input. For example, if N = 1,000,000, an O(N) algorithm may perform around 1,000,000 iterations, while an O(√N) algorithm may require only about 1,000. This complexity often appears when a mathematical property allows the algorithm to examine only values up to √N, such as checking possible factors when testing whether a number is prime.

`O(N)` Linear Time

O(N) means the amount of work grows directly in proportion to the input size. An algorithm typically has linear complexity when it processes each input element once, or a constant number of times. If the input doubles from N to 2N, the amount of work also approximately doubles. Traversing an array, searching an unsorted list, or calculating the sum of all elements are common examples of linear-time operations.

`O(N log N)` Linearithmic Time

O(N log N) combines linear processing with logarithmic reduction or division of the problem. A common pattern is that an algorithm processes about N elements across each of approximately log N levels. This occurs in efficient sorting algorithms such as Merge Sort. O(N log N) grows somewhat faster than O(N), but much more slowly than O(N²), which is why it is considered very efficient for many algorithms that must process or sort large collections

`O(N²)` Quadratic Time

O(N²) means the amount of work grows approximately with the square of the input size. This often happens when each of N elements must be processed against every other element, such as with two full nested loops. If the input doubles, the work increases by roughly four times because (2N)² = 4N². Quadratic algorithms may work well for small inputs but can become expensive quickly as N grows.

`O(N³)` Cubic Time

O(N³) means the amount of work grows approximately with the cube of the input size. It commonly appears when three dimensions or three full nested loops each depend on N. If the input doubles, the work increases by roughly eight times because (2N)³ = 8N³. Cubic algorithms therefore become expensive even faster than quadratic algorithms and are generally practical only when the input size is relatively small.

`O(2ᴺ)` Exponential Time

O(2ᴺ) commonly appears when an algorithm explores two choices for each of N elements, producing about 2ᴺ states. For example, subset backtracking explores 2ᴺ include/exclude combinations. If all subsets are actually copied and returned, generating the complete output takes Θ(N × 2ᴺ) time. The growth is extremely fast: N = 20 already gives more than one million possibilities, while N = 30 gives more than one billion. Exponential algorithms are therefore usually practical only for relatively small inputs.

`O(N!)` Factorial Time

O(N!) means the algorithm may need to examine every possible ordering of N elements. The number of possibilities grows as N × (N - 1) × (N - 2) × ... × 1, so adding even one more element can multiply the amount of work dramatically. For example, 5 elements have 120 possible permutations, while 10 elements already have 3,628,800. Factorial complexity grows even faster than exponential complexity and is generally feasible only for very small values of N. If every permutation is copied and returned, generating the complete output takes O(N × N!) time.

13. Recognizing Common Loop Patterns

Pattern	Typical Complexity
`i = i+1`	`O(N)`
`i = i+2`	`O(N)`
`i = i+100`	`O(N)`
`i = i×2`	`O(log N)`
`i = i ÷ 2`	`O(log N)`
Loop until `√N`	`O(√N)`
Two full nested `N` loops	`O(N²)`
Three full nested `N` loops	`O(N³)`

Increasing the loop variable by 2 is still O(N), not O(N/2), because Big O ignores constant factors.

14. Hidden Complexity

Code can perform expensive work even when no loop is visible. For example, nums.includes(target) may scan all N elements and therefore take O(N) worst-case time. Similarly, sorting followed by traversal costs O(N log N) + O(N), which simplifies to O(N log N). Always analyze what an operation actually does internally.

15. Recursive Algorithms

For recursive algorithms, analyze how many recursive calls are created, how quickly the input shrinks, the work performed in each call, and the maximum recursion depth. A single call on N - 1 often produces linear growth, halving the input often produces logarithmic growth, and creating multiple recursive branches can produce exponential growth.

Linear Recursion → Time: O(N), Space: O(N)

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Recursive Binary Search → Time: O(log N), Space: O(log N)

The input is halved after each recursive call: N→N/2→N/4→⋯

Branching Recursion

Naive Fibonacci: creates a rapidly growing recursion tree. A common simple upper bound is: O(2ᴺ)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

16. Common Big O Mistakes

Mistake	Correct Idea
Two loops always mean `O(N²)`	Sequential loops may still be `O(N)`
Two nested loops always mean `O(N²)`	Count actual iterations
`O(2 × N)` is different from `O(N)`?	No. Constant multipliers are ignored, so O(2 × N) simplifies to O(N).
Keep `N² + N + 1`	Keep dominant term: `O(N²)`
No visible loop means `O(1)`	Built-in methods can contain loops
Recursion uses no extra memory	Recursive calls use stack space
Big O measures seconds	Big O measures growth
`O(1)` means exactly one operation	It means constant work
Every input is called `N`	Independent inputs may require `N`, `M`, `V`, `E`, etc.

17. How to Calculate Space Complexity

Space complexity measures how much memory an algorithm uses as the input size grows. In most algorithm analysis, we focus on auxiliary space, which is the extra memory created by the algorithm, excluding the original input.

When calculating space complexity, ask: What additional memory grows as the input grows?Then keep the dominant growth term, just as with time complexity.
For example: O(N) + O(N) + O(1) → O(N)

Memory Used	Typical Space
Fixed number of variables	`O(1)`
New array of size `N`	`O(N)`
Two arrays of size `N`	`O(N)`
Two new arrays, size N and size M	`O(N + M)`
`N × N` matrix	`O(N²)`
Hash Set / Hash Map storing up to `N` items	`O(N)`
Recursion depth of `N`	`O(N)`
Recursion depth of `log N`	`O(log N)`

Example 1: Constant Space
Only a fixed number of variables are created, regardless of N. Auxiliary Space: O(1)

function sumArray(nums) {
  let sum = 0;

  for (const num of nums) {
    sum += num;
  }

  return sum;
}

Example 2: Linear Space
result grows to contain N elements. Auxiliary Space: O(N)

function doubleArray(nums) {
  const result = [];

  for (const num of nums) {
    result.push(num * 2);
  }

  return result;
}

Example 3: Recursive Space
There can be N recursive calls on the call stack at the same time. Auxiliary Space: O(N)

function countdown(n) {
  if (n === 0) return;

  countdown(n - 1);
}

Table of Contents