Tutorials Home   >   Problem-Solving & Logic Building   >   What Is Big-O Notation?

What Is Big-O Notation?

What Is Big-O Notation?

A Complete Explanation for Learners

1. Introduction: Why Do We Need Big-O Notation?

Imagine you write two programs that solve the same problem:

  • One finishes almost instantly

  • The other becomes slower as the input grows

How do we compare their efficiency without running them on every possible computer?

This is where Big-O Notation comes in.

Big-O Notation gives us a standard mathematical way to describe how an algorithm behaves as the input size grows. It helps programmers answer the question:

“How does this algorithm scale?”

Big-O is a core concept in:

  • Algorithms

  • Data structures

  • Competitive programming

  • Technical interviews

  • Software engineering

2. What Is Big-O Notation?

2.1 Definition

Big-O Notation describes the upper bound (worst-case) growth rate of an algorithm’s:

  • Time complexity (speed)

  • Space complexity (memory)

In simple terms:

Big-O tells us how fast the cost of an algorithm grows when the input size becomes very large.

2.2 What Big-O Does Not Measure

Big-O does not measure:

  • Actual execution time in seconds

  • Performance on a specific machine

  • Exact number of operations

Instead, it measures how performance grows.

3. Input Size and Growth Rate

3.1 Input Size (n)

We use n to represent input size:

  • Number of elements in an array

  • Length of a string

  • Number of nodes in a tree

Big-O answers:

“If n becomes very large, what happens?”

3.2 Why Growth Rate Matters More Than Speed

Example:

Algorithm n = 10 n = 1,000
O(n) 10 steps 1,000 steps
O(n²) 100 steps 1,000,000 steps

Even if the quadratic algorithm is faster for small inputs, it becomes much slower as n grows.

4. Worst-Case Analysis

4.1 Why Worst Case?

Big-O focuses on the worst case because:

  • It guarantees performance limits

  • It avoids unexpected slowdowns

  • It is safer for real systems

Example: Linear search

  • Best case: first element → O(1)

  • Worst case: last element → O(n)

Big-O uses O(n).

5. Common Big-O Notations (From Best to Worst)

5.1 O(1) – Constant Time

Time does not depend on input size.

Example:

x = arr[0]

No matter how big the array is, access time stays the same.

5.2 O(log n) – Logarithmic Time

Each step reduces the problem size.

Example:

  • Binary search

  • Balanced binary trees

If n = 1,000,000 → about 20 steps

5.3 O(n) – Linear Time

Time grows directly with input size.

Example:

for x in arr:
print(x)

Double the input → double the time.

5.4 O(n log n) – Linearithmic Time

Common in efficient sorting algorithms.

Examples:

  • Merge Sort

  • Heap Sort

  • Quick Sort (average case)

This is usually the best possible for comparison-based sorting.

5.5 O(n²) – Quadratic Time

Two nested loops over the input.

Example:

for i in range(n):
for j in range(n):
print(i, j)

Becomes slow quickly for large n.

5.6 O(2ⁿ) – Exponential Time

Time doubles with each additional input.

Example:

  • Naive recursive Fibonacci

Very inefficient and impractical for large inputs.

6. Rules for Writing Big-O Notation

6.1 Ignore Constants

O(3n) → O(n)
O(100) → O(1)

Constants do not affect growth rate.

6.2 Ignore Lower-Order Terms

O(n² + n) → O(n²)
O(n + log n) → O(n)

Only the fastest-growing term matters.

6.3 Nested Loops Multiply

  • One loop → O(n)

  • Two nested loops → O(n²)

6.4 Sequential Code Adds (Then Simplifies)

O(n) + O(n) = O(2n) → O(n)

7. Big-O for Recursive Algorithms

Example: Recursive Factorial

def fact(n):
if n == 1:
return 1
return n * fact(n - 1)

  • Function called n times

  • Time complexity → O(n)

  • Space complexity → O(n) (call stack)

8. Big-O vs Big-Ω vs Big-Θ

Notation Meaning
Big-O (O) Worst case
Big-Ω (Ω) Best case
Big-Θ (Θ) Average / tight bound

In practice:

Big-O is used most often.

9. Why Big-O Is So Important

Big-O helps:

  • Compare algorithms

  • Predict scalability

  • Write efficient code

  • Pass technical interviews

  • Design large systems

Without Big-O, programs may work for small data but fail at scale.

10. Common Beginner Mistakes

❌ Thinking Big-O measures speed
❌ Counting exact operations
❌ Ignoring worst case
❌ Forgetting space complexity

11. Developing Big-O Intuition

Ask yourself:

  • “How many times does this loop run?”

  • “Does input size affect memory?”

  • “What happens if n = 1 million?”

12. Summary

Big-O Notation:

  • Describes algorithm efficiency

  • Focuses on growth rate

  • Uses worst-case analysis

  • Ignores constants and small terms