Time Complexity

When we write an algorithm, it's not enough to know that it gives the correct answer. We also want to know how efficiently it works.

Imagine you have a program that searches through 10 numbers. Almost any reasonable solution will finish instantly.

Now imagine the same program has to search through 10 million numbers. Suddenly, the way you wrote the algorithm becomes very important.

This is where time complexity comes in.

Time complexity is a way of describing how the running time of an algorithm grows as the input size increases.

Why Do We Need Time Complexity?

Let's say we have an array:

int[] numbers = {10, 20, 30, 40, 50};

Suppose we want to find 50.

We could check every element one by one:

for (int number : numbers) {
    if (number == 50) {
        System.out.println("Found");
    }
}

If the array contains 5 elements, we may perform up to 5 comparisons.

But what if the array contains 1,000,000 elements?

In the worst case, we may have to check all 1,000,000 elements.

So as the input becomes larger, the amount of work also increases.

Time complexity helps us describe this growth.

What is Input Size?

In DSA, we usually represent the size of the input using n.

For example, if an array contains:

10 elements

then:

n = 10

If it contains:

1,000 elements

then:

n = 1,000

If an algorithm needs to look at every element, its amount of work grows as n grows.

We describe that as:

O(n)

This is called linear time complexity.

Big O Notation

You'll hear Big O notation constantly when studying DSA.

Big O is a way of describing the growth rate of an algorithm's time or space requirements as the input size increases.

Some common time complexities are:

O(1)       Constant
O(log n)   Logarithmic
O(n)       Linear
O(n log n) Linearithmic
O(n²)      Quadratic
O(2ⁿ)      Exponential
O(n!)      Factorial

Don't worry if these look confusing right now. We'll understand them one by one.

O(1) — Constant Time

An algorithm is O(1) when the amount of work doesn't depend on the size of the input.

For example:

int[] numbers = {10, 20, 30, 40, 50};

System.out.println(numbers[2]);

We are directly accessing the element at index 2.

Whether the array has 5 elements or 5 million elements, accessing a particular index takes approximately the same amount of work.

So we describe it as:

O(1)

Think of it as:

The input can grow, but the amount of work stays roughly the same.

O(n) — Linear Time

Now consider this:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

If n = 10, the loop runs 10 times.

If n = 100, it runs 100 times.

If n = 1,000, it runs 1,000 times.

The amount of work grows directly with the input size.

Therefore:

O(n)

This is called linear time.

A common example is searching through an unsorted array.

O(n²) — Quadratic Time

Now imagine a loop inside another loop:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + " " + j);
    }
}

The outer loop runs n times.

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

So the total number of operations is approximately:

n × n = n²

Therefore, the time complexity is:

O(n²)

This is called quadratic time.

For example:

n = 10    → 100 operations
n = 100   → 10,000 operations
n = 1000  → 1,000,000 operations

You can see how quickly the number of operations grows.

O(log n) — Logarithmic Time

Logarithmic algorithms are much more efficient for large inputs.

A classic example is binary search.

Imagine you have a sorted list of 1,000 numbers and you're looking for one particular number.

Instead of checking every number one by one, binary search repeatedly cuts the search area roughly in half.

For example:

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

Because the search space keeps getting divided, the algorithm has a time complexity of:

O(log n)

We'll learn binary search properly later, so for now, just remember that repeatedly reducing the problem by half often leads to logarithmic complexity.

O(n log n)

Some efficient sorting algorithms have a time complexity of:

O(n log n)

Examples include Merge Sort and, in typical cases, Quick Sort.

It is slower than O(n) but generally much better than O(n²) for large inputs.

You'll see this complexity frequently when studying sorting algorithms.

Why Do We Ignore Constants?

Suppose we have:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

Technically, we perform about 2n operations.

So you might think the complexity is:

O(2n)

But in Big O notation, we generally ignore constant factors.

So:

O(2n)

becomes:

O(n)

The reason is that we're interested in how the algorithm grows as n becomes very large, rather than the exact number of individual operations.

Similarly:

O(5n) → O(n)
O(100n) → O(n)
O(3n²) → O(n²)

Different Parts of an Algorithm

Suppose we have:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

Each loop is O(n).

Together:

O(n) + O(n)

which becomes:

O(2n)

and finally:

O(n)

Now consider:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);
    }
}

Here, the loops are nested, so we multiply their complexities:

O(n) × O(n)

giving:

O(n²)

This is a useful rule when analyzing simple code.

Time Complexity Is About Growth

One important thing to understand is that time complexity doesn't usually mean the exact number of seconds a program takes.

For example, saying an algorithm is O(n) doesn't mean:

"This algorithm takes exactly 1 second."

It means that as n grows, the amount of work grows approximately linearly with n.

The actual running time also depends on the computer, programming language, hardware, and other factors.

Time complexity gives us a way to compare algorithms independently of those details.

Best, Average, and Worst Case

An algorithm can sometimes behave differently depending on the input.

For example, suppose we're searching for a number in an array:

10, 20, 30, 40, 50

If we're searching for 10, we find it immediately.

If we're searching for 50, we may have to check every element.

So we can talk about different cases:

Best case: The algorithm finishes as quickly as possible.

Worst case: The algorithm has to do the maximum amount of work.

Average case: The expected amount of work for typical inputs.

When people casually say the "time complexity" of an algorithm, they're often referring to its worst-case Big O complexity, unless stated otherwise.

A Simple Comparison

Suppose we have four algorithms:

O(1)
O(log n)
O(n)
O(n²)

As the input gets larger, their growth looks roughly like:

Fast
 ↓
O(1)
O(log n)
O(n)
O(n²)
 ↓
Slower

For very large inputs, the difference can become enormous.

That's why choosing an efficient algorithm matters.

The Main Idea

Time complexity gives us a way to understand how an algorithm's running time grows as the input size increases.

The most important complexities to become familiar with are:

O(1)       → Constant
O(log n)   → Logarithmic
O(n)       → Linear
O(n log n) → Linearithmic
O(n²)      → Quadratic

You don't need to memorize everything immediately. As we solve more DSA problems, you'll naturally start recognizing these patterns in code.

The important question to develop while solving a problem is:

"As my input becomes larger, how much more work will my algorithm have to do?"

That question is at the heart of time complexity.