Note · New to DSA

How do I know the time complexity?

Part of the DSA Roadmap7 min read

When you start learning DSA, you’ll quickly come across things like:

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

At first, these can feel like something you simply have to memorize.

You don’t.

The basic idea is:

Time complexity describes how the amount of work your algorithm does grows as the input gets larger.

The easiest way to understand it is to look at your code.

01 — Start with the loops

Start with the loops

One loop → O(n)

If your code goes through all n elements once:

for each element:
    do something

The work grows with the size of the input.

10 elements → roughly 10 iterations
1,000 elements → roughly 1,000 iterations

ComplexityO(n)

Think:

I go through the input once.

Two loops, one after another → O(n)

for each element:
    do something

for each element:
    do something else

Each loop takes O(n), so technically O(n) + O(n) = O(2n). We ignore the constant and write:

ComplexityO(n)

The important distinction is that the loops are sequential, not nested.

Nested loops → O(n²)

for each element:
    for each element:
        do something

For every element in the outer loop, you’re going through the elements again. That gives n × n = n²:

ComplexityO(n²)

A useful mental model:

Sequential loops usually add. Nested loops usually multiply.

Three nested loops → O(n³)

for each element:
    for each element:
        for each element:
            do something

That’s n × n × n = n³:

ComplexityO(n³)

As you meet deeper nesting, ask yourself how many times the innermost operation can execute.

02 — Don't count exact operations

Don't count exact operations

Suppose your algorithm performs 3n + 5operations. You don’t write O(3n + 5).

Instead, we focus on how the algorithm grows as n becomes very large. The dominant term is n, so:

ComplexityO(n)

Similarly, 5n² + 20n + 100 becomes:

ComplexityO(n²)

The constants and lower-order terms are ignored.

03 — What does O(1) mean?

What does O(1) mean?

O(1) means the amount of work does not depend on the size of the input.

For example, if you access an element directly by its index:

array[5]

you’re asking for one specific position. Whether the array holds 10 elements or 10 million, the operation itself doesn’t require going through all of them.

ComplexityO(1)

Think:

The input can grow, but this particular operation stays roughly the same.

04 — What does O(log n) mean?

What does O(log n) mean?

You’ll meet this one in algorithms that repeatedly reduce the amount of work. A common example is an algorithm that halves the remaining search space each time:

n
n/2
n/4
n/8
n/16
...

Because the problem keeps getting smaller exponentially, the number of steps grows much more slowly than n.

ComplexityO(log n)

A useful question to ask is:

Does each step eliminate a significant portion of the remaining problem?

If the answer is yes, investigate whether the complexity is logarithmic.

05 — Sequential vs. nested work

Sequential vs. nested work

This one distinction will help you enormously.

Sequential

A → O(n)

B → O(n)

O(n + n)O(n)

Nested

A → O(n)
    B → O(n)

O(n × n)O(n²)

So when you look at your code, first ask:

Are these operations happening one after another, or is one happening inside another?

06 — What about space complexity?

What about space complexity?

The same general idea applies to memory.

Time complexity asks:

How much work does my algorithm do as the input grows?

Space complexity asks:

How much additional memory does my algorithm use as the input grows?

If your algorithm only uses a few variables regardless of the input size:

SpaceO(1)

If it creates another collection that could grow with the input:

SpaceO(n)

You’ll pick up the specific data structures and their memory characteristics as you work through the roadmap.

07 — A simple cheat sheet

A simple cheat sheet

Pattern	Complexity
Single operation	O(1)
One pass through the input	O(n)
Two sequential passes	O(n)
Nested pass	O(n²)
Three levels of nesting	O(n³)
Repeatedly halving the problem	O(log n)

These aren’t rules that cover every possible algorithm, but they’re a very useful starting point.

08 — Using this while solving problems

Using this while solving problems

Don’t try to determine the complexity before you understand your solution. Instead:

Step 1

Solve the problem

Write the simplest solution you can think of.

Step 2

Get it working

It is completely normal for your first implementation to fail. Run it, inspect the failure, change your code, and try again.

Step 3

Look at your code

Once it works, ask how many times this code can execute. Look at loops, nested loops, repeated operations, recursion, and any extra data structures you created.

Step 4

Estimate the complexity

Write down Time: O(?) and Space: O(?).

Step 5

Explain why

Don't just write O(n²) — say what makes it O(n²) in your own words.

Write something like:

The outer loop runs n times, and for each iteration the inner loop can also run n times, so the total work is n × n.

That explanation is much more valuable than memorizing the answer.

09 — Getting it wrong is part of it

Getting it wrong is part of it

When you’re learning DSA, you will sometimes think your solution is O(n) and later realize it’s O(n²). That’s normal.

The goal isn’t to instantly identify the correct Big-O for every piece of code. The goal is to build the habit of asking:

As the input gets bigger, how does the work my code performs grow?

With practice, you’ll start recognizing these patterns naturally.

Callout

Don’t memorize Big-O. Learn to see it in your code.