Time Complexity

Why Do We Need Time Complexity?

Imagine two algorithms that solve the same problem.

For 10 elements, both finish almost instantly.

Now give them 1 million elements.

One still finishes quickly.

The other takes so long that it becomes impractical.

Both algorithms are correct. The difference is how their work grows as the input grows.

That is what time complexity helps us understand.

We are not trying to predict whether your program takes exactly 2 ms or 5 ms.

We are asking a more useful question:

"What happens when the input becomes much larger?"

What Does Time Complexity Actually Measure?

Time complexity does not mean actual clock time.

Instead, we estimate the amount of work an algorithm performs.

Consider:

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

The loop runs once for every element.

If:

n = 10     → 10 iterationsn = 100    → 100 iterationsn = 10,000 → 10,000 iterations

The work grows directly with n.

So we describe it as:

O(n)

The important part is the growth, not the exact number of milliseconds.

Dropping the Smaller Terms

Big O introduced the rule: keep the fastest-growing term, drop the constants and everything below it. So 3n + 10 is O(n) and 5n² + 3n + 20 is O(n²).

Worth seeing once as arithmetic rather than as a rule, because it is the step people most often distrust:

The dropped terms never get smaller. 3n + 20 grows from 50 to 3,020 across those three columns. What changes is that they stop being a measurable share of the total, and by the time n is in the thousands the 5n² is 99.94% of the work.

The Complexity Classes You Need to Know

These are the patterns you will encounter repeatedly throughout DSA.

You do not need to memorize these blindly.

Let's understand the important ones through code.

O(1): Constant Time

Constant time means the amount of work does not depend on n.

first = arr[0]

Whether the array contains:

10 elements

or

10,000,000 elements

we perform one direct access.

So:

Time Complexity: O(1)

The input may grow, but the amount of work stays constant.

O(n): Linear Time

Consider:

for x in arr:    print(x)

If the array contains n elements, the loop runs n times.

n = 10       → 10 iterationsn = 100      → 100 iterationsn = 1,000    → 1,000 iterations

So:

Time Complexity: O(n)

This is one of the most common patterns in DSA.

A complete traversal of an array or string is usually O(n).

O(n²): Quadratic Time

Now put one loop inside another:

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

For every iteration of the outer loop, the inner loop runs n times.

Therefore:

n × n = n²

So:

Time Complexity: O(n²)

This pattern often appears when comparing every element with every other element.

For example, simple sorting algorithms such as Bubble Sort can have O(n²) time complexity.

O(log n): Logarithmic Time

Here is a very different pattern:

n↓n / 2↓n / 4↓n / 8↓...

The input is repeatedly reduced.

This is what happens in Binary Search.

Suppose there are 16 elements:

16 → 8 → 4 → 2 → 1

Only four reductions are needed.

For 1,024 elements:

1024 → 512 → 256 → ... → 1

Only about 10 reductions are needed.

Why?

2¹⁰ = 1024

So Binary Search runs in:

O(log n)

Whenever the problem size is repeatedly divided by a constant factor, think logarithmic.

O(n log n): Linearithmic Time

O(n log n) often appears when an algorithm repeatedly divides a problem and performs linear work at each level.

Merge Sort is the classic example.

The array is repeatedly divided:

n↓n/2 + n/2↓n/4 + n/4 + ...↓...

There are approximately log n levels, and each level processes n elements.

Therefore:

n × log n

So:

Merge Sort → O(n log n)

This is an important complexity because many efficient sorting algorithms operate around this range.

O(2ⁿ) and O(n!)

These are where things become expensive very quickly.

Exponential: O(2ⁿ)

A common example is generating all subsets of n elements.

Every element can either:

include it      orexclude it

That gives:

2 × 2 × 2 × ... = 2ⁿ

possible subsets.

Factorial: O(n!)

A common example is generating all permutations.

For n elements:

n × (n-1) × (n-2) × ... × 1 = n!

The growth is extremely fast.

That is why algorithms with O(2ⁿ) or O(n!) often become impractical even for relatively small inputs.

How to Analyze Code

You do not need to count every instruction.

Use a simple process.

1. Identify the input size

Ask:

What does n represent?

2. Find the repeated work

Look for:

• loops
• nested loops
• recursion
• repeated function calls
• operations that shrink or expand the input

3. Determine how often the work happens

Then express that growth mathematically.

4. Keep the dominant term

Finally, simplify it into Big O.

Let's practice.

One Loop → O(n)

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

The loop runs n times, so it is O(n).

Two Sequential Loops → O(n)

for i in range(n):    ... for j in range(n):    ...

The total work is:

n + n = 2n

Ignore the constant, and it is O(n).

Important

Two loops do not automatically mean O(n²).

It depends on whether they are nested or sequential.

Nested Loops → O(n²)

for i in range(n):    for j in range(n):        ...

The inner loop runs n times for each of the n outer iterations.

n × n = n²

Therefore it is O(n²).

Different Inputs → O(n + m)

Consider:

for i in range(n):    ... for j in range(m):    ...

The first loop depends on n.

The second depends on m.

So the total is O(n + m).

Do not automatically write O(n) just because both are loops.

Keep different input sizes separate unless you have a valid reason to relate them.

Look at How the Variable Changes

Counting loops is not the same as counting work, and this is the example that proves it.

Consider:

i = 1 while i < n:    i *= 2

The value doubles each time:

1 → 2 → 4 → 8 → 16 → 32 → ...

After approximately log₂ n iterations, i reaches n.

Therefore:

O(log n)

So do not look at a loop and immediately guess its complexity.

Look at how the variable changes.

Recursion

The list of things to look for includes recursion, so here is how to read one. Count how many calls each call makes, and how much smaller the input gets.

def fib(n):    if n <= 1:        return n    return fib(n - 1) + fib(n - 2)

Each call makes two more, and n drops by only one. So the calls double at every level and there are about n levels:

2 × 2 × 2 × ... = 2ⁿ

fib is O(2ⁿ), which is why the naive version becomes unusable somewhere around n = 40.

Now change one thing:

def binary(arr, target, lo, hi):    if lo > hi:        return -1    mid = (lo + hi) // 2    if arr[mid] == target:        return mid    if arr[mid] < target:        return binary(arr, target, mid + 1, hi)    return binary(arr, target, lo, mid - 1)

Each call makes one more, and the input halves. Halving reaches 1 in about log₂ n steps, so there are log n levels with one call each:

O(log n).

Those two numbers are the whole technique:

Best, Average, and Worst Case

The same algorithm can perform differently depending on the input.

Consider Linear Search:

for i in range(n):    if arr[i] == target:        return i

If the target is:

• first → very little work
• somewhere in the middle → moderate work
• last or missing → maximum work

When we discuss algorithmic complexity, worst-case complexity is often the most useful measure because it tells us the maximum growth we should be prepared for.

A Small but Important Detail: Constants

Suppose we have:

for i in range(n):    ... for i in range(n):    ...

Technically:

2n operations

But we write O(n). Why?

Because Big O focuses on the growth rate.

Whether the algorithm performs n, 2n, or 100n operations, all of them grow linearly with n.

So O(n) represents the same asymptotic growth.

Why This Matters in DSA

Imagine you need to search for a value in an array.

A simple linear search:

O(n)

A binary search on a sorted array:

O(log n)

For a small array, the difference may not matter.

For a very large array, it matters enormously.

This is the reason DSA is not only about:

"Can you solve the problem?"

It is also about:

"Can you solve it efficiently?"

When you learn a data structure or algorithm, you should always ask:

What operation am I performing?        ↓How much work does it require?        ↓How does that work grow with n?

That is the beginning of algorithmic thinking.

Common Mistakes

Quick Check

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

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

i = 1 while i < n:    i *= 2

for i in range(n):    ... for j in range(m):    ...

Quick Recap

• Time complexity describes how an algorithm's work grows with input size.
• n usually represents the size of the input.
• Big O describes the algorithm's asymptotic growth.
• O(1) → constant
• O(log n) → logarithmic
• O(n) → linear
• O(n log n) → linearithmic
• O(n²) → quadratic
• O(2ⁿ) → exponential
• O(n!) → factorial
• Sequential loops usually add.
• Nested loops usually multiply.
• Repeatedly reducing the input often produces O(log n).
• Best, average, and worst cases can be different.
• Big O describes growth, not exact execution time.

Where This Leads

You now know how to answer one of the most important questions in DSA:

"How does this algorithm scale?"

But time is only half of the story.

An algorithm can be fast while using a large amount of memory, or use very little memory while doing much more work.

That brings us to the next question:

How much memory does an algorithm need as the input grows?

→ Next: Space Complexity