Unit 1 · Foundation of DSA

Algorithm Complexity Cheat Sheet

A quick DSA complexity cheat sheet with common Big O values, examples, rules, and revision notes for interviews.

Introduction

This chapter gives you a quick reference for common time and space complexities used in DSA.

Use it when you need to revise Big O patterns, compare algorithms, or quickly identify the complexity of loops and recursion.

The goal is not memorization alone. The goal is to recognize patterns in code.

Fastest to Slowest
O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n) -> O(n!)

How This Cheat Sheet Helps

Fast Revision

Review common complexities in one place.

Pattern Recognition

Map loops and algorithms to Big O quickly.

Interview Prep

Use standard complexity vocabulary confidently.

Better Choices

Pick efficient solutions by comparing growth rates.

Common Code Patterns
Common Data Structure Operations
Simplification Rules
Space Complexity Patterns

Common Code Patterns

Most beginner complexity questions can be solved by recognizing common patterns in loops and data structures.

Direct access by index: O(1).
Single loop from 0 to n: O(n).
Loop that halves input each time: O(log n).
Two nested loops over n: O(n^2).
Sorting with merge sort or heap sort: O(n log n).

Common Data Structure Operations

Different data structures have different operation costs. Choosing the right one can change the whole solution.

Array access by index is O(1).
Array search without sorting is O(n).
Stack push and pop are O(1).
Queue enqueue and dequeue are O(1).
Hash table average search is O(1).

Simplification Rules

Big O expressions are simplified because we care about long-term growth, not small constants.

O(5) becomes O(1).
O(2n) becomes O(n).
O(n + 100) becomes O(n).
O(n^2 + n) becomes O(n^2).
O(n * log n) is written as O(n log n).

Space Complexity Patterns

Space complexity mainly depends on extra memory, not the input itself unless the problem asks for total memory.

Few variables: O(1).
Extra array of size n: O(n).
2D matrix of n by n: O(n^2).
Recursive stack depth n: O(n).

Complexity Cheat Sheet Table

Complexity	Performance	Example
O(1)	Excellent	Array index access
O(log n)	Very good	Binary search
O(n)	Good	Linear traversal
O(n log n)	Good for sorting	Merge sort
O(n^2)	Slow for large input	Nested comparison
O(2^n)	Very slow	Subset generation
O(n!)	Extremely slow	All permutations

C Program Example

This nested loop prints all pairs, so its time complexity is O(n^2).

#include <stdio.h>

int main() {
    int n = 3;

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

    return 0;
}

Output: (0,0) (0,1) (0,2) (1,0) ...

Key Points

O(1), O(log n), O(n), O(n log n), and O(n^2) are the most common beginner complexities.
Nested loops often indicate quadratic time.
Extra arrays and recursion stacks affect space complexity.
Always simplify Big O by ignoring constants and smaller terms.

Interview Tip

When stuck, write down how many times the most expensive line runs.

Common Beginner Mistakes

Memorizing tables without understanding code patterns.
Forgetting that input size can be n, m, rows, columns, or nodes.
Calling every nested loop O(n^2) even when loop limits are different.

Quick Revision

One loop: O(n).
Nested n by n loops: O(n^2).
Halving each step: O(log n).
Extra array: O(n) space.

Summary

This cheat sheet summarizes the most common complexity patterns used in DSA. With practice, you can identify time and space complexity by reading loops, recursion, and data structure operations.