Practice & Reference

Use the cheat sheet for quick reference, and learn about common mistakes to avoid in your complexity analysis.

Big O Cheat Sheet

Time Complexity

Notation	Name	Example Patterns	n=10	n=100	n=1000
O(1)	Constant	Array access by index, Arithmetic operations	1.0	1.0	1.0
O(log n)	Logarithmic	Binary search, Balanced tree operations	3.3	6.6	10.0
O(n)	Linear	Single loop through array, Linear search	10	100	1K
O(n log n)	Linearithmic	Merge Sort, Quick Sort (average)	33	664	10K
O(n²)	Quadratic	Nested loops, Bubble Sort	100	10K	1M
O(2^n)	Exponential	Naive Fibonacci, Subset generation	1K	> 1T	> 1T

O(1)Constant

Operations take the same time regardless of input size

Flat line - no growth

O(log n)Logarithmic

Operations grow slowly as input doubles

Slow curve - grows very slowly

O(n)Linear

Operations grow proportionally with input size

Straight line - proportional growth

O(n log n)Linearithmic

Slightly worse than linear, common in efficient sorting

Gentle curve - manageable growth

O(n²)Quadratic

Operations grow with the square of input size

Steep curve - grows quickly

O(2^n)Exponential

Operations double with each additional input

Explosive - impractical for large inputs

Space Complexity Quick Reference

Pattern	Space Complexity	Example
Single variables	O(1)	int x, y, z;
Array of size n	O(n)	int[] arr = new int[n];
2D array n×n	O(n²)	int[][] matrix = new int[n][n];
Recursive call stack (depth d)	O(d)	recursive calls to depth d

Key Rules to Remember

Drop Constants

O(2n) = O(n)
O(n² + 1000) = O(n²)

Drop Lower Terms

O(n² + n) = O(n²)
O(n + log n) = O(n)

Sequential = Addition

O(n) then O(m)
= O(n + m)

Nested = Multiplication

O(n) inside O(m)
= O(n × m)

Common Mistakes to Avoid

Mistake: "Nested loops always mean O(n²)"

void process(int[] arr) {
    for (int i = 0; i < arr.length; i++) {     // n times
        for (int j = 0; j < 5; j++) {           // 5 times (constant!)
            System.out.println(arr[i] + j);
        }
    }
}
// This is O(n), NOT O(n²)!

Correct understanding:

The inner loop runs a fixed 5 times, not n times. 5n operations = O(n). Only when BOTH loops depend on n do we get O(n²).

Mistake: "Two O(n) loops make O(n²)"

void twoLoops(int[] arr) {
    // First loop: O(n)
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
    // Second loop: O(n)
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i] * 2);
    }
}
// This is O(n) + O(n) = O(2n) = O(n), NOT O(n²)!

Correct understanding:

Sequential (one after another) operations ADD. Nested operations MULTIPLY. O(n) + O(n) = O(2n) = O(n). Only O(n) × O(n) = O(n²).

Mistake: "Constants matter in Big O"

What students think:

O(2n) is worse than O(n)
O(n² + 1000) is worse than O(n²)
O(n/2) is better than O(n)

Reality:

O(2n) = O(n)
O(n² + 1000) = O(n²)
O(n/2) = O(n)

Correct understanding:

Big O cares about growth rate, not exact count. Constants and lower-order terms become insignificant as n grows large. We always simplify to the dominant term.

Mistake: Confusing best, worst, and average case

Consider linear search:

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Best Case

O(1)

Target is first element

Average Case

O(n/2) = O(n)

Target is in middle

Worst Case

O(n)

Target is last or missing

Remember:

When we say an algorithm is O(n), we usually mean the worst case. This is the most useful measure because it gives an upper bound guarantee.

Ready to Practice?

Exercises

Practice identifying Big O from code snippets with immediate feedback.

Quiz

Test your understanding with conceptual and code tracing questions.