If you’re starting your LeetCode journey, you’ve probably seen people throw around terms like O(n), O(log n), or even the terrifying O(2ⁿ).

At first, these symbols can feel intimidating, but they’re actually just a way of answering one simple question:

How does my algorithm scale as the input gets bigger?

Big O notation measures the time complexity (or sometimes space complexity) of an algorithm. It doesn’t tell you exactly how many milliseconds your code takes—it tells you how the runtime grows as the input size (n) increases.

A good algorithm isn’t just one that works—it should also remain efficient as the input grows.

The Big O Complexity Ranking

From fastest to slowest, the most common time complexities are:

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Let’s break down what each one means.

🟢 O(1) — Constant Time

The runtime stays the same regardless of how large the input becomes.

Whether your array has 10 elements or 10 million, the operation still takes one step.

Example: Array Access

value = nums[5]

Common LeetCode examples

  • Accessing an array element
  • HashMap lookup
  • Stack push/pop

This is the gold standard of efficiency.

🟢 O(log n) — Logarithmic Time

Instead of checking every element, the algorithm repeatedly cuts the search space in half.

Every step eliminates half of the remaining possibilities.

Example: Binary Search

1000 elements
↓
500
↓
250
↓
125
↓
...

Even for a million elements, binary search only needs around 20 comparisons.

Common LeetCode examples

  • Binary Search
  • Searching in a sorted array
  • Finding insertion position

🟡 O(√n) — Square Root Time

These algorithms don’t examine every number—they only go up to the square root of n.

A classic example is checking whether a number is prime.

Instead of checking every divisor up to n, we only check until √n.

Example

To determine if 100 is prime:

Instead of testing numbers from 2 to 99, we only test up to 10.

Common LeetCode examples

  • Trial division
  • Prime checking
  • Factorization

🟡 O(n) — Linear Time

The runtime grows directly with the size of the input.

If the input doubles, the work roughly doubles.

Example

for num in nums:
    print(num)

Every element is visited exactly once.

Common LeetCode examples

  • Array traversal
  • Finding the maximum element
  • Two Pointer problems
  • Sliding Window techniques

🟠 O(n log n) — Linearithmic Time

This complexity is slightly slower than linear but still considered very efficient.

You’ll mostly encounter it in sorting algorithms.

Examples

  • Merge Sort
  • Heap Sort
  • Quick Sort (average case)

If a problem requires sorting an array first, expect an O(n log n) solution.

🔴 O(n²) — Quadratic Time

Usually caused by nested loops.

For every element, you iterate through the entire array again.

for i in nums:
    for j in nums:
        ...

If the input doubles, the runtime becomes roughly four times larger.

Common LeetCode examples

  • Comparing every pair
  • Brute-force duplicate search
  • Matrix traversal with nested loops

For small inputs this is acceptable, but for large inputs it often leads to Time Limit Exceeded (TLE).

🔴 O(n³) — Cubic Time

Now we’re dealing with three nested loops.

for i:
    for j:
        for k:
            ...

These solutions become slow very quickly.

You’ll rarely see optimal LeetCode solutions with cubic complexity unless the input size is very small.

🚨 O(2ⁿ) — Exponential Time

Every additional element doubles the amount of work.

This commonly appears when generating every possible subset or recursively exploring every choice.

Examples

  • Subset generation
  • Naive recursion
  • Backtracking without pruning

Even a small increase in input size can make the runtime explode.

n = 10 → 1,024 possibilities
n = 20 → 1,048,576 possibilities

💀 O(n!) — Factorial Time

This is the slowest complexity you’ll commonly encounter.

Factorial algorithms generate every possible ordering of elements.

Example

The brute-force solution to the Traveling Salesman Problem checks every possible route.

5 cities → 120 routes
10 cities → 3,628,800 routes
15 cities → over 1 trillion routes

Factorial growth becomes impractical almost immediately.

Which Complexities Are Good for LeetCode?

A simple rule of thumb:

Complexity

Good?

O(1)

✅ Excellent

O(log n)

✅ Excellent

O(√n)

✅ Very Good

O(n)

✅ Great

O(n log n)

✅ Usually Accepted

O(n²)

⚠️ Depends on input size

O(n³)

❌ Usually Too Slow

O(2ⁿ)

❌ Avoid if possible

O(n!)

💀 Almost Never

Final Thoughts

Big O notation isn’t about memorizing symbols—it’s about developing an intuition for how your code behaves as the input grows.

As you solve more LeetCode problems, you’ll start recognizing patterns:

  • Binary Search → O(log n)
  • Two Pointers → O(n)
  • Sliding Window → O(n)
  • Sorting → O(n log n)
  • Nested loops → O(n²)
  • Backtracking → Often O(2ⁿ)

The goal isn’t always to find a solution—it’s to find one that’s efficient enough to pass the constraints.

The more you practice analyzing time complexity before writing code, the faster you’ll improve at solving coding interview problems.