Learn DSA Part 1: Time and Space Complexity (Big-O) Explained with Examples

Before you learn a single data structure, you need a way to answer one question: how does my solution behave when the input gets big? That is what time and space complexity measure. Every DSA interview expects you to state the complexity of your solution and explain why, and every later article in this series uses the ideas below.

This first part of the Learn DSA series covers Big-O notation, the complexities you will meet most often, how to analyse loops and recursion step by step, space complexity, and amortized analysis. Code examples are in C++ and Java.

1. What complexity really measures

Running time in seconds depends on the machine, the language and the compiler, so we do not use it to compare algorithms. Instead we count how the number of basic operations grows as the input size n grows. An algorithm that does about 3n + 5 operations and one that does n + 100 operations both grow linearly, so both are O(n).

Three notations describe this growth:

In interviews, people say "Big-O" but usually mean the tight bound of the worst case. For example, linear search is O(n) in the worst case (the item is last or missing) but O(1) in the best case (the item is first).

2. The common complexities and how big n can be

A modern judge or machine does very roughly 10^8 simple operations per second. That rule of thumb tells you which complexity you need just from the input limits in a problem statement.

3. How to analyse loops step by step

Most code is loops, and four rules cover almost all of them:

• Sequential blocks add: a loop of n followed by another loop of n is O(n + n) = O(n).
• Nested loops multiply: a loop of n inside a loop of n is O(n x n) = O(n^2).
• Halving or doubling gives log n: if the loop variable is divided or multiplied by 2 each time, the loop runs about log2(n) times.
• Drop constants and smaller terms: O(2n^2 + 7n + 3) is just O(n^2), because for large n the n^2 term dominates.

// O(n^2): count pairs (i, j), i < j, with a[i] + a[j] == target
int countPairs(const vector<int>& a, int target) {
    int n = a.size(), count = 0;
    for (int i = 0; i < n; i++)          // runs n times
        for (int j = i + 1; j < n; j++)  // runs n-1, n-2, ..., 1 times
            if (a[i] + a[j] == target) count++;
    return count;                        // about n*(n-1)/2 checks
}

// O(log n): how many times can n be halved before reaching 1?
int halvings(int n) {
    int steps = 0;
    while (n > 1) { n /= 2; steps++; }
    return steps;
}

// O(n^2): count pairs (i, j), i < j, with a[i] + a[j] == target
static int countPairs(int[] a, int target) {
    int n = a.length, count = 0;
    for (int i = 0; i < n; i++)          // runs n times
        for (int j = i + 1; j < n; j++)  // runs n-1, n-2, ..., 1 times
            if (a[i] + a[j] == target) count++;
    return count;                        // about n*(n-1)/2 checks
}

// O(log n): how many times can n be halved before reaching 1?
static int halvings(int n) {
    int steps = 0;
    while (n > 1) { n /= 2; steps++; }
    return steps;
}

In countPairs the inner loop runs n-1, then n-2, and so on down to 1 time. The total is n(n-1)/2, which is still O(n^2) after dropping constants. In halvings, n goes n, n/2, n/4 ... 1, which takes about log2(n) steps.

4. Complexity of recursive functions

For recursion, write a recurrence: the cost for input n in terms of the cost of smaller inputs. Then count the work across the whole recursion tree.

// Time O(2^n), extra space O(n) for the recursion stack
long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// Time O(2^n), extra space O(n) for the recursion stack
static long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Each call to fib makes two more calls, so the tree roughly doubles at every level and has about n levels: around 2^n calls (more precisely about 1.6^n). That is why naive Fibonacci is exponential, and why dynamic programming (Part 13) brings it down to O(n).

For divide-and-conquer recurrences of the form T(n) = aT(n/b) + O(n^d), the Master Theorem gives the answer directly: compare d with log_b(a). If they are equal the answer is O(n^d log n), as in merge sort where a = 2, b = 2 and d = 1.

5. Space complexity and the hidden recursion stack

Space complexity counts the extra memory your algorithm uses as n grows, usually called auxiliary space. The input itself is normally not counted.

• Using a few variables: O(1) space.
• Building a new array or hash map of size n: O(n) space.
• A 2D DP table of n x m: O(n x m) space.
• Recursion uses stack space: every call that has not returned yet keeps a stack frame. Naive fib(n) uses O(n) stack space because the deepest chain of calls is n long, even though it makes about 2^n calls in total.

Interviewers often ask a follow-up like "can you do it in O(1) extra space?". Patterns such as two pointers (Part 4) exist mostly to answer that question.

6. Amortized complexity

Some operations are usually cheap but occasionally expensive. Amortized complexity is the average cost per operation over a long sequence of operations.

The classic example is a dynamic array (vector in C++, ArrayList in Java). When it is full, it allocates an array twice as large and copies everything, which costs O(n). But this happens so rarely that n pushes cost O(n) in total, so each push is O(1) amortized. Hash map operations are similar: O(1) on average, with an occasional O(n) resize.

Practice problems

Work out the time complexity of each snippet before reading the answer. These are the kind of quick checks interviewers ask.

1. for (i = 1; i < n; i *= 2) with an O(1) body. Answer: O(log n).
2. for (i = 0; i < n; i++) for (j = 0; j < i; j++). Answer: O(n^2), about n^2/2 iterations.
3. for (i = 0; i < n; i++) for (j = 1; j < n; j *= 2). Answer: O(n log n).
4. A loop of n followed by a separate loop of m. Answer: O(n + m), not O(n x m).
5. Recursive function that calls itself once on n/2 and does O(n) work per call. Answer: O(n), since n + n/2 + n/4 + ... is at most 2n.
6. Sorting an array, then one pass over it. Answer: O(n log n); the sort dominates.