Time and Space Complexity: Understanding Algorithm Efficiency

Introduction#

When we write a program, it is not enough to know whether it gives the correct output.

We also want to understand:

• How much time does the program take as the input grows?
• How much memory does the program use?
• Will the program still work efficiently when the input becomes very large?

This is where time complexity and space complexity are useful.

They help us understand the efficiency of an algorithm.

---

What is Time Complexity?#

Time complexity describes how the number of operations performed by an algorithm grows as the size of the input increases.

Consider accessing an element from an array:

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

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

We directly access the element at index 2.

Whether the array contains 5 elements or 5 million elements, accessing an element using its index takes approximately the same amount of time.

So the time complexity is:

O(1)

Now consider a loop:

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

If n is 10, the loop runs 10 times.

If n is 100, it runs 100 times.

If n is 1000, it runs 1000 times.

So the number of operations grows with the input size.

---

What is Big O Notation?#

We use Big O notation to describe how the number of operations grows as the input size increases.

Some common time complexities are:

Big O	Name	Example
O(1)	Constant	Accessing an array element
O(log n)	Logarithmic	Binary search
O(n)	Linear	Loop through an array
O(n log n)	Linearithmic	Efficient sorting algorithms
O(n²)	Quadratic	Nested loops

Big O focuses on the growth of the algorithm rather than the exact number of seconds it takes.

---

O(1) — Constant Time#

O(1) means the number of operations does not grow with the input size.

Example:

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

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

We directly access the element at index 2.

Whether the array contains 5 elements or 5 million elements, accessing a particular index is a constant-time operation.

So this is:

O(1)

---

O(n) — Linear Time#

O(n) means the number of operations grows linearly with the input size.

Example:

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

If n increases, the number of loop iterations also increases.

n = 10      → 10 iterations
n = 100     → 100 iterations
n = 1000    → 1000 iterations

Therefore, the time complexity is:

O(n)

A common example is searching through an array one element at a time.

---

O(n²) — Quadratic Time#

O(n²) usually occurs when we have a loop inside another loop.

Example:

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

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

So the total number of operations is approximately:

n × n = n²

Therefore:

O(n²)

For example:

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

This shows why algorithms with quadratic growth can become expensive as the input gets larger.

---

O(log n) — Logarithmic Time#

O(log n) means the problem size is reduced significantly during each step.

A common example is binary search.

Suppose we have a sorted array:

[10, 20, 30, 40, 50, 60, 70]

Instead of checking every element one by one, binary search checks the middle element and eliminates half of the remaining elements.

The search space keeps getting smaller:

7 elements
   ↓
3 elements
   ↓
1 element

This gives a time complexity of:

O(log n)

Binary search is useful when the data is sorted and we want to search efficiently.

---

O(n log n) - Linearithmic Time#

Some algorithms have a time complexity of O(n log n).

This is commonly seen in efficient sorting algorithms such as merge sort.

The important thing to understand at this stage is that:

O(n log n)

grows faster than O(n) but slower than O(n²) as the input becomes large.

---

Comparing Common Time Complexities#

We can roughly think about the growth like this:

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

As the input size becomes very large, the difference between these growth rates becomes important.

For example, an O(n²) solution may work for a small input but become too slow when the input is very large.

---

How to Find Time Complexity from Code#

A simple way to start is to look at how many times the main operation runs.

Consider:

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

The loop runs n times.

Therefore:

O(n)

Now consider:

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:

n × n = n²

Therefore:

O(n²)

The basic idea is to look at how the number of operations grows as n grows.

---

Space Complexity#

Time complexity tells us about the growth of the number of operations.

Space complexity tells us about the additional memory an algorithm needs as the input size grows.

For example:

int number = 10;

Only a fixed amount of additional memory is required.

So its additional space complexity is:

O(1)

Now consider:

int[] numbers = new int[n];

The array needs space for n elements.

As n increases, the required memory also increases.

Therefore:

O(n)

---

O(1) Space Complexity#

Consider:

int sum = 0;

for (int i = 0; i < n; i++) {
    sum += i;
}

The loop runs n times, so the time complexity is:

O(n)

But we are only using a few variables regardless of n.

Therefore, the additional space complexity is:

O(1)

This is an important point:

Time complexity and space complexity can be different for the same program.

Here:

Time Complexity  → O(n)
Space Complexity → O(1)

---

O(n) Space Complexity#

Consider:

int[] numbers = new int[n];

The amount of memory required grows with n.

Therefore:

Space Complexity = O(n)

For example:

n = 10      → space for 10 elements
n = 100     → space for 100 elements
n = 1000    → space for 1000 elements

---

Time and Space Complexity Together#

Let's look at this example:

int[] numbers = new int[n];

for (int i = 0; i < n; i++) {
    numbers[i] = i;
}

The loop runs n times.

Therefore:

Time Complexity  → O(n)
Space Complexity → O(n)

The array requires memory that grows with n, while the loop takes time that grows with n.

---

Why Do We Learn Complexity?#

Imagine two programs solve the same problem.

One program takes:

O(n)

and another takes:

O(n²)

For a small input, the difference might not be noticeable.

But when the input becomes very large, their performance can be very different.

Understanding complexity helps us:

• Choose appropriate algorithms
• Understand how programs behave with large inputs
• Reduce unnecessary operations
• Use memory efficiently
• Compare different solutions to the same problem

---

Understanding Constraints#

When solving coding problems, we are usually given constraints for the input.

For example:

1 ≤ n ≤ 10^5

This means the maximum value of n can be:

n = 100,000

The constraint is important because it gives us an idea of how efficient our solution needs to be.

What Happens with O(n²)?#

Suppose:

n = 10^5

If our algorithm has O(n²) time complexity:

n² = 10^5 × 10^5
   = 10^10
   = 10,000,000,000

That is 10 billion operations.

A solution that performs around 10 billion operations will generally be too slow for a typical coding problem.

So when we see a constraint such as:

n ≤ 10^5

we should be careful about using an O(n²) solution.

Depending on the problem, we would usually look for an O(n) or O(n log n) approach.

---

Choosing Time Complexity Based on Constraints#

The input constraint helps us understand what kind of time complexity we should aim for.

For example:

Constraint	Commonly Considered Complexity
n ≤ 10	O(2^n) or even O(n!) may be possible
n ≤ 20	O(2^n) may be possible
n ≤ 1,000	O(n²) may be possible
n ≤ 10^5	O(n) or O(n log n) is commonly expected
n ≤ 10^6	Usually O(n) is preferred
n very large, such as 10^9	Often O(log n) or a mathematical approach is needed

These are only rough guidelines.

The actual choice depends on the problem, the number of test cases, the time limit, and what each operation does.

The main idea is:

The larger the input constraint, the more efficient our algorithm needs to be.

---

Constraints and Choosing the Data Type#

Constraints also help us decide which data type to use.

Suppose the problem gives:

1 ≤ n ≤ 10^5

So the maximum value of n is:

n = 100,000

An int can store this value because Java's int range is:

-2,147,483,648 to 2,147,483,647

But we also need to think about the calculation we perform.

Suppose our calculation involves n².

n² = 10^5 × 10^5
   = 10^10
   = 10,000,000,000

The maximum value that an int can store is:

2,147,483,647

But:

10,000,000,000 > 2,147,483,647

So 10^10 is outside the range of int.

Therefore, we need to use long to store the result.

int n = 100000;

long result = (long) n * n;

System.out.println(result);

Output:

10000000000

---

Why Do We Write (long)?#

Consider:

int n = 100000;

long result = n * n;

Even though result is a long, the calculation:

n * n

is performed using int because both n values are int.

The value 10,000,000,000 cannot fit inside an int, so integer overflow can occur.

Instead, convert one value to long before the multiplication:

long result = (long) n * n;

Now the multiplication is performed using long.

This is why we should consider the maximum value of the calculation, not just the maximum value of the input.

---

int vs long#

A simple way to remember the ranges is:

Data Type	Approximate Range
int	-2.1 × 10^9 to 2.1 × 10^9
long	-9.2 × 10^18 to 9.2 × 10^18

---

A Simple Approach to Solving DSA Problems#

When you see a new coding problem, don't immediately start writing code.

First, look at the constraints.

Understand the maximum input#

For example:

n ≤ 10^5

Ask:

How large can the input become?

Check the maximum possible result#

Ask:

How large can my calculation become?

This helps you decide whether int is enough or whether you need long.

Think about the straightforward solution#

For example:

Nested loops → O(n²)

Compare the complexity with the constraint#

If:

n ≤ 10^5

and your solution is:

O(n²)

calculate the approximate number of operations:

(10^5)² = 10^10

That should make you question whether the approach is efficient enough.

---

Check Your Understanding#

Question 1

What is the time complexity of this code?

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

Question 2

What is the time complexity of this code?

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

Question 3

Suppose:

n = 100000

What is n²?

Would the following code safely store the result?

int n = 100000;
int result = n * n;

If not, which data type should be used and why?