Algorithm Complexity

Algorithm complexity measures how efficiently an algorithm uses time and memory as the input size increases.

It is one of the most important concepts in Data Structures and Algorithms (DSA).

1. Why Complexity Matters

Suppose we want to search for a number in an array:

A = [10, 25, 30, 45, 60, 75, 90]

For a small array, almost any algorithm seems fast.

But imagine:

n = 1,000,000,000

An inefficient algorithm could take an extremely long time.

Complexity lets us predict how an algorithm behaves as n grows.

2. Two Main Types of Complexity

A. Time Complexity

Measures how much time/number of operations an algorithm requires.

Example:

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

The loop executes n times.

Therefore:

$$T(n) = O(n)$$ 

This is called linear time.

B. Space Complexity

Measures how much additional memory an algorithm requires.

Example:

int sum = 0;

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

Only a few variables are used regardless of n.

Therefore:

$$S(n) = O(1)$$ 

This is constant space.

3. Big-O Notation

The most commonly used notation is Big-O.

Big-O describes the growth rate of an algorithm.

Common complexities, from generally best to worst:

The important idea is:

$$\boxed{\text{As }n\text{ increases, how quickly does the work grow?}}$$ 

4. O(1) — Constant Complexity

The algorithm performs approximately the same amount of work regardless of input size.

int first = arr[0];

Whether the array contains:

10 elements

or

10,000,000 elements

accessing arr[0] takes constant-time work.

Therefore:

$$\boxed{O(1)}$$ 

Example

int getFirst(int arr[]) {
    return arr[0];
}

5. O(n) — Linear Complexity

Work increases directly with input size.

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

If:

n = 10      → 10 iterations
n = 100     → 100 iterations
n = 1,000   → 1,000 iterations

Therefore:

$$\boxed{O(n)}$$ 

Example: Linear Search

int search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }

    return -1;
}

Worst case:

$$O(n)$$ 

because we may need to inspect every element.

6. O(log n) — Logarithmic Complexity

The input is repeatedly reduced by a factor, commonly by half.

The classic example is Binary Search.

Suppose:

n = 16

Binary search reduces the search space:

16 → 8 → 4 → 2 → 1

Only about:

$$\log_2(16)=4$$ 

steps are needed.

Therefore:

$$\boxed{O(\log n)}$$ 

Binary Search

int binarySearch(int arr[], int n, int x) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == x)
            return mid;

        if (arr[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

Requirement: the array must be sorted.

7. O(n²) — Quadratic Complexity

Usually occurs when one loop is nested inside another.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << " " << j;
    }
}

The outer loop executes n times.

For each outer iteration, the inner loop executes n times.

Therefore:

$$n \times n = n^2$$ 

So:

$$\boxed{O(n^2)}$$ 

Example

For:

n = 10

approximately:

100 operations

For:

n = 1,000

approximately:

1,000,000 operations

This illustrates why quadratic algorithms become expensive quickly.

8. O(n³) — Cubic Complexity

Three nested loops commonly produce cubic complexity:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // operation
        }
    }
}

Therefore:

$$n \times n \times n = n^3$$ 

$$\boxed{O(n^3)}$$ 

9. O(n log n)

This is an important complexity in efficient sorting algorithms.

Examples include:

• Merge Sort
• Heap Sort
• Average-case Quick Sort

Conceptually, an algorithm may divide the problem into smaller pieces:

$$\log n$$ 

while processing approximately:

$$n$$ 

elements at each level.

Thus:

$$\boxed{O(n\log n)}$$ 

10. Exponential Complexity — O(2ⁿ)

Exponential algorithms grow extremely rapidly.

A simple example:

int fib(int n) {
    if (n <= 1)
        return n;

    return fib(n - 1) + fib(n - 2);
}

The naive recursive Fibonacci algorithm has approximately:

$$\boxed{O(2^n)}$$ 

time complexity.

For large nthis becomes impractical.

Using dynamic programming can reduce Fibonacci calculation to:

$$O(n)$$ 

11. Factorial Complexity — O(n!)

Factorial complexity is even worse.

For example, generating every possible permutation of n objects requires:

$$n!$$ 

possibilities.

For:

n = 5

$$5! = 120$$ 

For:

n = 10

$$10! = 3,628,800$$ 

For:

n = 20

$$20! = 2,432,902,008,176,640,000$$ 

This is why brute-force permutation algorithms become infeasible very quickly.

12. Comparing Growth Rates

A useful order to memorize is:

$$\boxed{ O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) }$$ 

As n becomes very large, algorithms toward the right generally become much less practical.

13. How to Calculate Time Complexity

Consider:

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

The loop runs n times:

$$T(n)=n$$ 

Therefore:

$$\boxed{O(n)}$$ 

Example 2

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

Number of operations:

$$n \times n = n^2$$ 

Therefore:

$$\boxed{O(n^2)}$$ 

Example 3

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

for (int j = 0; j < n; j++) {
    cout << j;
}

The loops are sequential, not nested:

$$n+n=2n$$ 

Drop the constant:

$$\boxed{O(n)}$$ 

14. Important Rules for Big-O

Rule 1 — Ignore constants

If:

$$T(n)=5n$$ 

then:

$$\boxed{O(n)}$$ 

Not O(5n).

Rule 2 — Keep the dominant term

If:

$$T(n)=n^2+n+10$$ 

the dominant term is:

$$n^2$$ 

Therefore:

$$\boxed{O(n^2)}$$ 

Rule 3 — Sequential operations are usually added

O(n) + O(n)

becomes:

$$O(2n)=O(n)$$ 

Rule 4 — Nested operations are usually multiplied

O(n) × O(n)

becomes:

$$\boxed{O(n^2)}$$ 

15. Best, Average and Worst Case

Complexity can also be analyzed according to the input situation.

Consider linear search:

[10, 20, 30, 40, 50]

Searching for 10:

1 comparison

Searching for 30:

3 comparisons

Searching for 50:

5 comparisons

Searching for something that doesn’t exist:

5 comparisons

So:

16. Complexity and Data Structures

Complexity is closely connected to data structures.

For example:

*Hash-table complexities are typically average-case; worst-case behavior can differ.

This is why choosing the correct data structure is critical.

17. Time vs Space Trade-off

Sometimes we can make an algorithm faster by using more memory.

For example, suppose we repeatedly need to determine whether a value exists.

A naive approach might search an array every time:

$$O(n)$$ 

per lookup.

If we build a hash table, lookup can be approximately:

$$O(1)$$ 

on average.

But the hash table requires additional memory.

This is called a:

$$\boxed{\text{Time-Space Trade-off}}$$ 

18. A Practical Example

Suppose you have:

int arr[1000000];

and need to find a value.

Linear Search

O(n)

Potentially up to one million elements examined.

Binary Search

If the array is sorted:

O(log n)

Approximately:

$$\log_2(1,000,000)\approx20$$ 

comparisons.

That’s a dramatic difference.

19. Complexity Analysis Cheat Sheet

20. What You Should Master

For DSA, learn algorithm complexity in this order:

Algorithm
   ↓
Input size n
   ↓
Count basic operations
   ↓
Construct T(n)
   ↓
Remove constants
   ↓
Keep dominant term
   ↓
Big-O complexity

For example:

for (int i = 0; i < n; i++) {       // n
    for (int j = 0; j < n; j++) {   // n
        // operation
    }
}

Therefore:

$$T(n)=n\times n=n^2$$ 

and finally:

$$\boxed{O(n^2)}$$ 

Key takeaway

Algorithm complexity is fundamentally about scalability. An algorithm that works perfectly for n = 100 may be unusable for n = 1,000,000. Learning to recognize O(1), O(log n), O(n), O(n log n), O(n²), and exponential growth is the foundation for analyzing algorithms and choosing efficient data structures.