Understanding Complexity Classes with Examples

Last Updated on April 16, 2026 by Rajeev Bagra

When learning algorithms, one of the most important concepts is time complexity — how the running time of a program grows as the input size increases.

If an algorithm works fine for 10 items, will it still work for 10,000 or 1 million items?

That is where complexity classes help us.

In this guide, we’ll explain the most common complexity classes with simple examples.

Examples:

• Number of elements in a list
• Number of records in a database
• Number of users on a platform
• Number of nodes in a graph

---

1. Constant Time —

An algorithm takes the same amount of time regardless of input size.

Whether the array has 5 items or 5 million items, the work stays nearly the same.

Example

arr = [10, 20, 30, 40]
print(arr[2])

Accessing an element by index is constant time.

Real World Examples

• Checking first item in queue
• Reading value from dictionary/hash table (average case)
• Turning on a switch

Why It’s Great

This is one of the best possible complexities.

---

2. Logarithmic Time —

The problem size is reduced by half (or by a fixed fraction) every step.

Example: Binary Search

Suppose we search in:

[2, 5, 7, 9, 11, 15, 20]

To find “11”:

1. Check middle → “9”
2. Go right half
3. Check middle again
4. Found “11”

Why Powerful?

If:

Then binary search takes only around:

steps.

Real World Examples

• Searching sorted data
• Guessing number games
• Efficient database lookups

---

3. Linear Time —

The time grows directly with input size.

Double input size = roughly double time.

Example

Finding max in a list:

nums = [4, 8, 2, 9, 1]

Need to inspect every item once.

Real World Examples

• Counting all users
• Reading every email
• Summing list values

---

4. Log-Linear Time —

Very common in efficient sorting algorithms.

Example Algorithms

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

Why?

The list is divided repeatedly:

levels

And each level processes all items:

So total:

Why Important?

This is considered excellent for sorting large datasets.

---

5. Polynomial Time —

Where:

is a constant.

Examples:

• 
• 
• 

---

Quadratic Time —

Usually from two nested loops.

Example

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

If:

Then operations may be around:

Real World Uses

• Bubble sort
• Comparing every pair
• Duplicate checks (naive)

---

Cubic Time —

Three nested loops.

Example

for i in range(n):
for j in range(n):
for k in range(n):
pass

Used in some matrix algorithms.

---

6. Exponential Time —

Where:

Examples:

• 
• 

Growth becomes extremely fast.

Example: All Subsets

For a set with:

elements, number of subsets is:

If:

Then:

Huge.

Real World Examples

• Brute force password search
• Trying all combinations
• Some optimization problems

---

Comparison Table

Complexity| Meaning| Good for Large Input?
| Constant| Excellent
| Logarithmic| Excellent
| Linear| Good
| Efficient sorting| Good
| Quadratic| Medium
| Exponential| Poor

---

How to Recognize Complexity in Code

No Loop

Usually:

One Loop

Usually:

Nested Loops

Usually:

Divide by 2 Repeatedly

Usually:

Sorting

Usually:

Recursive Branching Choices

Often:

or worse.

---

Why This Matters in Real Business Applications

When your app grows from 100 users to 1 million users:

• Efficient algorithms save server cost
• Faster systems improve user experience
• Better scalability supports growth
• Lower compute cost improves profit margins

---

Final Thoughts

Big-O and Theta notation are not just academic concepts.

They help developers predict whether software will remain fast as data grows.

A slow algorithm may look fine with 10 records — but collapse with 1 million.

That is why great engineers care deeply about complexity.

---

Quick Rule of Thumb

Aim as close as possible to:

• 
• 
• 

Be cautious with:

• and above

---

If you master complexity classes, you begin thinking like a real computer scientist.