Space and Time Complexity in DSA

Imagine two students are given the same programming problem. Both write programs that produce the correct answer. However, one program gives the result in a second, while the other takes several minutes when the input becomes large.

Both programs work, but are they equally efficient?

This is where time complexity and space complexity become important. They help us understand how efficiently an algorithm uses a computer’s resources.

1. What Is Complexity in DSA?

In DSA, complexity refers to the resources an algorithm needs to solve a problem.

We mainly study two types:

• Time Complexity: How many operations does an algorithm need to perform as the amount of input data increases?
• Space Complexity: How much additional memory does an algorithm need as the amount of input data increases?

For example, finding a student’s name in a list of 10 students is usually easier than finding the same name in a list of 10 million students.

The important question is not simply how long the program takes on your computer. It is how its resource requirements change as the amount of data grows.

2. Understanding Input Size (n)

Before studying complexity, we need to understand one small term: n.

In algorithm analysis, n usually represents the size of the input.

For example:

• If an array contains 10 elements, n = 10.
• If a list contains 100 elements, n = 100.
• If a program processes 1,000 student records, n = 1,000.

We use n to describe how an algorithm behaves when the amount of input increases.

3. What Is Time Complexity?

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

Let’s understand this with a simple example.

Suppose we have an array:

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

We want to find the number 40.

One way is to check each element until we find the required number.

for (int i = 0; i < 5; i++) {
    if (numbers[i] == 40) {
        printf("Found");
        break;
    }
}

If the required number is at the beginning, we find it quickly. If it is at the end, we check every element.

Now imagine the array contains 1,000 or 1 million elements. The number of checks may also increase.

This is called linear time complexity, represented as:

O(n)

It means that the amount of work grows in proportion to the input size.

4. Common Types of Time Complexity

Let’s look at some common time complexities with simple examples.

A. Constant Time . O(1)

An algorithm has constant time complexity when the number of operations does not grow with the input size.

For example, accessing an array element using its index:

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

printf("%d", numbers[2]);

Whether the array contains 5 elements or 5,000 elements, accessing an element by its index takes a constant number of operations.

B. Linear Time . O(n)

The amount of work grows with the input size.

For example, printing every element of an array:

for (int i = 0; i < n; i++) {
    printf("%d", numbers[i]);
}

If there are 10 elements, the loop runs 10 times. If there are 100 elements, it runs 100 times.

C. Quadratic Time . O(n²)

Quadratic time often occurs when one loop runs inside another loop, and both depend on the input size.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%d %d\n", i, j);
    }
}

If n = 10, the inner operation runs 100 times. If n = 100, it runs 10,000 times.

As the input grows, the amount of work increases much faster.

D. Logarithmic Time . O(log n)

An algorithm has logarithmic time complexity when it repeatedly reduces the problem size, often by half.

Imagine searching for a word in a dictionary. Instead of checking every page, you open somewhere near the middle and decide which half to search. You repeat this process until you find the word.

This is the basic idea behind binary search, which we will study in detail in Article 11.

E. Linearithmic Time . O(n log n)

This complexity appears in efficient sorting algorithms such as Merge Sort.

We will understand how Merge Sort works in Article 13.

5. What Is Big O Notation?

ou have probably noticed expressions such as O(1), O(n), and O(n²) in the examples above.

These expressions are written using Big O notation.

Big O notation helps us understand how the amount of work performed by an algorithm grows as the input size increases. In simple words, it tells us how an algorithm’s efficiency changes when it has to process more data.

Let’s understand this with an example.

Suppose an algorithm performs approximately 3n + 5 operations, where n represents the input size.

If the input size is 10: 3 × 10 + 5 = 35 operations

If the input size is 100: 3 × 100 + 5 = 305 operations

As you can see, the amount of work increases with the input size.

However, most of this growth comes from 3n. The additional 5 operations become relatively insignificant as the input gets larger.

Therefore, we represent 3n + 5 as O(n).

Now consider another expression:

n² + 3n + 2

When the input size is 10:

• n² = 100
• 3n = 30
• 2 = 2
• Total = 132 operations

When the input size is 100:

• n² = 10,000
• 3n = 300
• 2 = 2
• Total = 10,302 operations

Notice how quickly the n² term grows compared with the other terms. As the input becomes larger, it contributes most of the overall work.

Therefore, we represent n² + 3n + 2 as O(n²).

Why do we ignore smaller terms and constant factors?

Big O focuses on the overall growth pattern rather than the exact number of operations.

For this reason, we follow two simple rules:

1. Ignore constant multipliers: For example, 5n is represented as O(n).
2. Keep the fastest-growing term: For example, n² + 3n + 2 is represented as O(n²).

In short, Big O notation helps us compare algorithms by showing how their resource requirements grow as the input size increases.

6. Best Case, Average Case, and Worst Case

An algorithm may perform differently depending on the input it receives.

Consider searching for a number in an array using linear search.

• Best Case: The number is at the first position. We find it immediately.
• Average Case: The number is somewhere in the middle, so we check several elements.
• Worst Case: The number is at the last position or is not present at all. We may have to check every element.

These are three ways of analysing an algorithm’s performance.

When discussing Big O, we commonly describe the worst-case growth, but Big O itself is an upper-bound notation, not another name for the worst case.

7. What Is Space Complexity?

Time complexity tells us about the growth of an algorithm’s work. Space complexity tells us about its memory requirements.

Every program needs some memory to store data and perform operations. However, some algorithms require additional memory beyond the input they receive.

Consider this example:

int sum = 0;

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

The algorithm uses only a few extra variables, regardless of how many elements are in the array.

Its auxiliary space complexity is O(1), meaning the extra memory used does not grow with the input size.

Now consider another example:

int copy[n];

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

Here, we create another array to store a copy of the original elements.

If the input contains 10 elements, the new array stores 10 elements. If the input contains 1,000 elements, it stores 1,000 elements.

The additional memory grows with the input size, so its auxiliary space complexity is O(n).

Remember: Space complexity is often discussed in terms of auxiliary space—the extra memory an algorithm uses, excluding the input itself. The exact convention should be stated when analysing an algorithm.

8. Time Complexity vs. Space Complexity

Sometimes, an algorithm can save time by using additional memory. In other situations, it may use less memory but perform more operations.

The goal is to find a suitable balance based on the problem and available resources.

9. Quick Comparison of Common Complexities

Here is a quick reference to help you remember the common growth patterns:

Generally, for sufficiently large inputs, algorithms with slower-growing complexity are preferable, provided they solve the same problem correctly and other practical factors are considered.

Understanding time and space complexity helps us look beyond whether a program works. It helps us understand whether it will continue to perform well when the amount of data increases.

As we study arrays, linked lists, searching, sorting, trees, graphs, and other data structures, we will repeatedly use these concepts to compare different approaches.

The goal is not simply to write a program that gives the correct answer. It is to find an efficient way to get that answer.

What’s Next?

In Article 4, we will study Data Types, Objects, and Data Structures: Representation and Implementation. We will understand how data is represented in a program and how different structures are implemented.