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.

Time complexity describes how the amount of work performed by an algorithm grows with its input size.

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 n Mean?

Before measuring an algorithm, we need to describe the size of its input.

We usually call that size n.

For example:

• An array with 10 elements → n = 10
• An array with 1,000 elements → n = 1,000
• A string with 500 characters → n = 500

The meaning of n depends on the problem.

For an array:

n = number of elements

For a graph, we might use:

V = number of verticesE = number of edges

So always ask:

"What exactly does the input size represent?"

That small habit prevents many complexity mistakes.

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.

Big O: The Language of Growth

Suppose an algorithm performs:

3n + 10 operations

As n becomes very large, the 3n term dominates the constant 10.

So we simplify:

3n + 10  →  O(n)

Similarly:

5n² + 3n + 20  →  O(n²)

We focus on the dominant growth.

The basic rule

When expressing Big O:

• Ignore constant multipliers.
• Ignore lower-order terms.
• Keep the fastest-growing term.

For example:

O(5n)       → O(n) O(2n + 10)  → O(n) O(n² + n)   → O(n²) O(3n³ + n)  → O(n³)

You do not need to calculate every operation.

You need to recognize how the work grows.

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.

O(n)

Simple.

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:

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:

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.

Not Every Nested Loop Is O(n²)

This is an important one.

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.

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.

Big O Is Not a Stopwatch

This is one of the most important things to understand.

Suppose:

Algorithm A → O(n)Algorithm B → O(n²)

It does not mean A will always be faster for every possible input.

For small inputs, constants and implementation details can matter.

Big O tells us how the algorithms scale as the input becomes large.

Think of it as a model of growth, not an exact execution-time measurement.

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):    ...

5n² + 3n + 20

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