W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Time & Space Complexity

Understand algorithm efficiency with Big O notation, asymptotic analysis & Master Theorem.

Topics

Minutes

C++

Language

Quick Complexity Reference

Complexity	Name	n=10	n=100	n=1000	Example
O(1)	Constant	1	1	1	Array access
O(log n)	Logarithmic	3	7	10	Binary search
O(n)	Linear	10	100	1,000	Single loop
O(n log n)	Linearithmic	33	664	9,966	Merge sort
O(n²)	Quadratic	100	10,000	1,000,000	Nested loops
O(2ⁿ)	Exponential	1,024	10³⁰	∞	Recursive fib

What is Time Complexity?

Time Complexity measures algorithm efficiency

Interactive

Loading Visualizer...

Understanding Growth Rates

Imagine preparing dinner for a party. If boiling a single pot of water takes 10 minutes, it will take the exact same 10 minutes whether you are serving 1 guest or 10 guests. This represents Constant Time (O(1)). However, peeling potatoes scales directly with the number of guests: peeling 10 potatoes takes 10 times longer than peeling 1. This represents Linear Time (O(n)).

Time Complexity is the mathematical framework we use to describe how the execution time of an algorithm grows as the size of the input (n) increases toward infinity.

Why We Need It:

Hardware Independence: It measures the count of fundamental operational steps rather than physical seconds, meaning your analysis remains valid whether run on a smartwatch or a supercomputer.
Scaling Predictions: It highlights how your code behaves under heavy stress (e.g., handling millions of database queries).
Comparison Standard: It provides an objective way to compare different solutions to the same problem.

Essential Rules:

Count Operations, Not Seconds: We count statements like assignments, loops, and condition checks.
Focus on the Bottleneck: We drop constant factors and lower-order terms because they become insignificant as n grows. For instance, an algorithm requiring 2n + 100 steps simplifies to O(n).

Quick Growth Benchmarks:

Array Lookup (Constant): Fetching an element directly by index → O(1)
Simple Search (Linear): Inspecting every single element one-by-one → O(n)
Double-Nested Loops (Quadratic): Running an inner loop of size n inside an outer loop of size n → O(n²)

C++ Code — What is Time Complexity?

// How to count operations?

// O(1) - Constant: Same operations regardless of n
int first = arr[0];  // 1 operation

// O(n) - Linear: Operations grow with n
for (int i = 0; i < n; i++) {  // n operations
    cout << arr[i];
}

// O(n²) - Quadratic: Nested loops
for (int i = 0; i < n; i++) {      // n
    for (int j = 0; j < n; j++) {  // × n
        cout << i + j;              // = n² operations
    }
}

// O(log n) - Logarithmic: Halving
while (n > 1) {  // log₂(n) times
    n = n / 2;
}

Asymptotic Notations

O (Upper) | Ω (Lower) | Θ (Tight Bound)

Interactive

Loading Visualizer...

Asymptotic Notations

Asymptotic notations are mathematical shorthand symbols used to establish the boundary limits of an algorithm's growth.

1. Big O (`O`) — Upper Bound (Worst Case)

Provides a maximum limit guarantee: "the execution will never take longer than this".
This is the standard metric used in technical interviews to represent worst-case constraints.
Definition: f(n) <= c * g(n) for all n >= n₀ (where c and n₀ are constants).

2. Big Omega (`Ω`) — Lower Bound (Best Case)

Provides a minimum limit guarantee: "the execution will take at least this long under the most optimal conditions".
Definition: f(n) >= c * g(n) for all n >= n₀.

3. Big Theta (`Θ`) — Tight Bound (Average Case)

Provides an exact boundary: the upper and lower bounds grow at the same rate, wrapping the function tightly from both sides.
Definition: c₁ * g(n) <= f(n) <= c₂ * g(n) for all n >= n₀.

Case Study: Linear Search

Best Case (Ω(1)): The target item happens to be the very first element (stops in 1 comparison).
Worst Case (O(n)): The target item is at the end of the array or missing entirely (must inspect all n items).
Average Case (Θ(n)): The target item lies somewhere in the middle (requires n/2 operations, which simplifies to linear growth).

C++ Code — Asymptotic Notations

// Linear Search Analysis

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

/*
Best Case: Ω(1)
- Target is at arr[0]
- Only 1 comparison needed

Worst Case: O(n)  
- Target is at arr[n-1] or not present
- n comparisons needed

Average Case: Θ(n)
- On average, check half the array
- n/2 comparisons → still O(n)

We usually say: Linear Search is O(n)
(We report worst case with Big O)
*/

Common Time Complexities

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Interactive

Loading Visualizer...

Time Complexity Hierarchy

An algorithm's efficiency dictates its performance. Here is the hierarchy sorted from most efficient (fastest) to least efficient (slowest):

O(1) — Constant Time ⭐ Best
- Execution time remains identical regardless of input size.
- Examples: Accessing an array element by index (arr[5]), pushing onto a stack.
O(log n) — Logarithmic Time
- The search space is cut in half at each step.
- Examples: Binary Search, querying balanced BST nodes.
O(n) — Linear Time
- The steps grow direct-proportionally with the input size.
- Examples: Iterating through an array, sum calculations.
O(n log n) — Linearithmic Time
- Typical of efficient sorting operations that repeatedly divide and merge.
- Examples: Merge Sort, Quick Sort (average), Heap Sort.
O(n²) — Quadratic Time
- Execution time scales with the square of the input.
- Examples: Nested loops, Bubble Sort, comparing all items in a set against each other.
O(2ⁿ) — Exponential Time ❌ Unstable
- Operations double with each single addition to the input size.
- Examples: Recursive Fibonacci, generating all subsets of a collection.
O(n!) — Factorial Time ❌ Worst
- Grows incredibly fast; becomes slow even for small inputs (n > 12).
- Examples: Brute force Traveling Salesman, generating all permutations.

C++ Code — Common Time Complexities

// Quick Reference

// O(1) - Constant
arr[5];  // Direct access
stack.push(x);

// O(log n) - Logarithmic
binarySearch(arr, target);
while (n > 1) n /= 2;

// O(n) - Linear
for (int x : arr) sum += x;
linearSearch(arr, target);

// O(n log n) - Linearithmic
sort(arr.begin(), arr.end());
mergeSort(arr);

// O(n²) - Quadratic
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        // ...

// O(2ⁿ) - Exponential
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// Which to choose for n = 1,000,000?
// O(n²) = 1,000,000,000,000 ops ❌ Too slow!
// O(n log n) = 20,000,000 ops ✅ Fast!

How to Calculate Time Complexity

Drop constants, keep highest order term

Steps to Calculate Complexity

Use these five rules of thumb to audit and calculate the complexity of your scripts:

Rule 1: Drop the Constants

We ignore multiplier coefficients because we only care about scale.

O(2n) simplifies to O(n)
O(300) simplifies to O(1)

Rule 2: Keep the Dominant Term

If you have multiple terms added together, drop the slower-growing ones.

O(n² + n) → O(n²) (quadratic growth dwarfs linear growth)
O(n + log n) → O(n)

Rule 3: Keep Different Inputs Separate

If an algorithm works on multiple unrelated inputs, represent them separately.

Two sequential loops over separate arrays A and B → O(A + B)
Two nested loops over separate arrays A and B → O(A * B)

Rule 4: Trace the Loop Traversal

Iterating step-by-step (+1) → O(n)
Iterating by multiplying/dividing by 2 → O(log n)

Rule 5: Calculate Recursive depth

Total complexity is the number of recursive branches multiplied by the work done in each call.

C++ Code — How to Calculate Time Complexity

// Examples of Calculation

// Example 1: Simple loop
for (int i = 0; i < n; i++) {  // O(n)
    cout << i;                   // O(1)
}
// Total: O(n) × O(1) = O(n)

// Example 2: Nested loops
for (int i = 0; i < n; i++) {      // O(n)
    for (int j = 0; j < n; j++) {  // O(n)
        arr[i][j] = i + j;         // O(1)
    }
}
// Total: O(n) × O(n) × O(1) = O(n²)

// Example 3: Sequential loops (ADD)
for (int i = 0; i < n; i++) {...}  // O(n)
for (int j = 0; j < m; j++) {...}  // O(m)
// Total: O(n) + O(m) = O(n + m)

// Example 4: Logarithmic
for (int i = 1; i < n; i *= 2) {  // O(log n)
    cout << i;
}
// i = 1, 2, 4, 8... 2^k = n → k = log n

// Example 5: Half loop
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {  // n-i times
        // ...
    }
}
// Total: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Master Theorem

T(n) = aT(n/b) + O(n^k)

The Master Theorem

The Master Theorem provides a quick, formulaic shortcut to evaluate divide-and-conquer recurrences of the following mathematical shape:

T(n) = a * T(n / b) + O(nᵏ)

Understanding the Variables:

a: The count of recursive subproblems generated at each division (a >= 1).
b: The factor by which the input size is divided (b > 1).
nᵏ: The non-recursive work required to divide the problem and merge the results back.

The Three Canonical Cases:

Mathematical Condition	Case	Resulting Time Complexity	Primary Bottleneck
`k < log_b(a)`	Case 1	`T(n) = Θ(n ^ log_b(a))`	Leaf subproblems dominate
`k = log_b(a)`	Case 2	`T(n) = Θ(nᵏ * log n)`	Work is balanced evenly
`k > log_b(a)`	Case 3	`T(n) = Θ(nᵏ)`	Root node work dominates

Real-World Examples:

Merge Sort: T(n) = 2T(n/2) + O(n)
- Here, a = 2, b = 2, k = 1.
- Since log_b(a) = log₂(2) = 1, we match Case 2 → Θ(n log n).
Binary Search: T(n) = T(n/2) + O(1)
- Here, a = 1, b = 2, k = 0.
- Since log_b(a) = log₂(1) = 0, we match Case 2 → Θ(log n).

C++ Code — Master Theorem

// Master Theorem Examples

// 1. Merge Sort: T(n) = 2T(n/2) + O(n)
void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);     // T(n/2)
        mergeSort(arr, m+1, r);   // T(n/2)
        merge(arr, l, m, r);      // O(n)
    }
}
// a=2, b=2, k=1 → log₂(2)=1=k → Case 2 → Θ(n log n)

// 2. Binary Search: T(n) = T(n/2) + O(1)
int binarySearch(vector<int>& arr, int t, int l, int r) {
    if (l > r) return -1;
    int m = (l + r) / 2;
    if (arr[m] == t) return m;
    if (arr[m] > t) return binarySearch(arr, t, l, m-1);
    return binarySearch(arr, t, m+1, r);
}
// a=1, b=2, k=0 → log₂(1)=0=k → Case 2 → Θ(log n)

// 3. Strassen's Matrix: T(n) = 7T(n/2) + O(n²)
// a=7, b=2, k=2 → log₂(7)≈2.81 > k → Case 1 → Θ(n^2.81)

Space Complexity

Auxiliary Space: Extra memory used by algorithm

Interactive

Loading Visualizer...

Space Complexity

Space Complexity tracks the maximum amount of active memory an algorithm consumes throughout its execution relative to the input size n.

Key Distinctions:

Auxiliary Space: The extra memory allocated by the algorithm excluding the input data itself. This is the primary metric evaluated by interviewers.
Total Space: The total memory consumed (Input space + Auxiliary space).

Standard Space Benchmarks:

O(1) — Constant Space: Memory remains static (e.g., swapping variables, simple loop counters).
O(log n) — Logarithmic Space: Typically occurs due to recursive stack frames (e.g., the depth of recursive divide-and-conquer).
O(n) — Linear Space: Memory scales direct-proportionally (e.g., dynamic arrays, hash map indexes, linear recursion call stack depth).
O(n²) — Quadratic Space: Memory scales quadratically (e.g., 2D grids, graph adjacency matrices).

The Memory-Time Tradeoff:

Developers often sacrifice memory to buy speed:

Caching/Hashing: Using a Hash Map (O(n) space) to get O(1) lookup speeds.
Dynamic Programming: Storing answers to overlapping subproblems in memory to prevent costly recalculation.

C++ Code — Space Complexity

// Space Complexity Examples

// O(1) - Constant Space
void swap(int& a, int& b) {
    int temp = a;  // Just 1 extra variable
    a = b;
    b = temp;
}

// O(n) - Linear Space
vector<int> copy(vector<int>& arr) {
    vector<int> result(arr.size());  // n elements
    for (int i = 0; i < arr.size(); i++) {
        result[i] = arr[i];
    }
    return result;
}

// O(n) - Recursion Call Stack
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // n stack frames!
}

// O(1) vs O(n) - Same problem, different space
// Fibonacci O(n) space
int fibRecursive(int n) {  // O(n) stack space
    if (n <= 1) return n;
    return fibRecursive(n-1) + fibRecursive(n-2);
}

// Fibonacci O(1) space ✅ Better!
int fibIterative(int n) {
    int a = 0, b = 1;  // Only 2 variables
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Complexity

Name

n=10

n=100

n=1000

Example

O(1)

Constant

Array access

O(log n)

Logarithmic

Binary search

O(n)

Linear

100

1,000

Single loop

O(n log n)

Linearithmic

664

9,966

Merge sort

O(n²)

Quadratic

100

10,000

1,000,000

Nested loops

O(2ⁿ)

Exponential

1,024

10³⁰

∞

Recursive fib

// How to count operations? // O(1) - Constant: Same operations regardless of n int first = arr[0]; // 1 operation // O(n) - Linear: Operations grow with n for (int i = 0; i < n; i++) { // n operations cout << arr[i]; } // O(n²) - Quadratic: Nested loops for (int i = 0; i < n; i++) { // n for (int j = 0; j < n; j++) { // × n cout << i + j; // = n² operations } } // O(log n) - Logarithmic: Halving while (n > 1) { // log₂(n) times n = n / 2; }

Asymptotic Notations

Asymptotic notations are mathematical shorthand symbols used to establish the boundary limits of an algorithm's growth.

1. Big O (`O`) — Upper Bound (Worst Case)

Provides a maximum limit guarantee: "the execution will never take longer than this".
This is the standard metric used in technical interviews to represent worst-case constraints.
Definition: f(n) <= c * g(n) for all n >= n₀ (where c and n₀ are constants).

2. Big Omega (`Ω`) — Lower Bound (Best Case)

Provides a minimum limit guarantee: "the execution will take at least this long under the most optimal conditions".
Definition: f(n) >= c * g(n) for all n >= n₀.

3. Big Theta (`Θ`) — Tight Bound (Average Case)

Provides an exact boundary: the upper and lower bounds grow at the same rate, wrapping the function tightly from both sides.
Definition: c₁ * g(n) <= f(n) <= c₂ * g(n) for all n >= n₀.

Case Study: Linear Search

Best Case (Ω(1)): The target item happens to be the very first element (stops in 1 comparison).
Worst Case (O(n)): The target item is at the end of the array or missing entirely (must inspect all n items).
Average Case (Θ(n)): The target item lies somewhere in the middle (requires n/2 operations, which simplifies to linear growth).

// Linear Search Analysis int linearSearch(vector<int>& arr, int target) { for (int i = 0; i < arr.size(); i++) { if (arr[i] == target) return i; } return -1; } /* Best Case: Ω(1) - Target is at arr[0] - Only 1 comparison needed Worst Case: O(n) - Target is at arr[n-1] or not present - n comparisons needed Average Case: Θ(n) - On average, check half the array - n/2 comparisons → still O(n) We usually say: Linear Search is O(n) (We report worst case with Big O) */

// Quick Reference // O(1) - Constant arr[5]; // Direct access stack.push(x); // O(log n) - Logarithmic binarySearch(arr, target); while (n > 1) n /= 2; // O(n) - Linear for (int x : arr) sum += x; linearSearch(arr, target); // O(n log n) - Linearithmic sort(arr.begin(), arr.end()); mergeSort(arr); // O(n²) - Quadratic for (i = 0; i < n; i++) for (j = 0; j < n; j++) // ... // O(2ⁿ) - Exponential int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); } // Which to choose for n = 1,000,000? // O(n²) = 1,000,000,000,000 ops ❌ Too slow! // O(n log n) = 20,000,000 ops ✅ Fast!

// Examples of Calculation // Example 1: Simple loop for (int i = 0; i < n; i++) { // O(n) cout << i; // O(1) } // Total: O(n) × O(1) = O(n) // Example 2: Nested loops for (int i = 0; i < n; i++) { // O(n) for (int j = 0; j < n; j++) { // O(n) arr[i][j] = i + j; // O(1) } } // Total: O(n) × O(n) × O(1) = O(n²) // Example 3: Sequential loops (ADD) for (int i = 0; i < n; i++) {...} // O(n) for (int j = 0; j < m; j++) {...} // O(m) // Total: O(n) + O(m) = O(n + m) // Example 4: Logarithmic for (int i = 1; i < n; i *= 2) { // O(log n) cout << i; } // i = 1, 2, 4, 8... 2^k = n → k = log n // Example 5: Half loop for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // n-i times // ... } } // Total: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Mathematical Condition

Case

Resulting Time Complexity

Primary Bottleneck

k < log_b(a)

Case 1

T(n) = Θ(n ^ log_b(a))

Leaf subproblems dominate

k = log_b(a)

Case 2

T(n) = Θ(nᵏ * log n)

Work is balanced evenly

k > log_b(a)

Case 3

T(n) = Θ(nᵏ)

Root node work dominates

// Master Theorem Examples // 1. Merge Sort: T(n) = 2T(n/2) + O(n) void mergeSort(vector<int>& arr, int l, int r) { if (l < r) { int m = (l + r) / 2; mergeSort(arr, l, m); // T(n/2) mergeSort(arr, m+1, r); // T(n/2) merge(arr, l, m, r); // O(n) } } // a=2, b=2, k=1 → log₂(2)=1=k → Case 2 → Θ(n log n) // 2. Binary Search: T(n) = T(n/2) + O(1) int binarySearch(vector<int>& arr, int t, int l, int r) { if (l > r) return -1; int m = (l + r) / 2; if (arr[m] == t) return m; if (arr[m] > t) return binarySearch(arr, t, l, m-1); return binarySearch(arr, t, m+1, r); } // a=1, b=2, k=0 → log₂(1)=0=k → Case 2 → Θ(log n) // 3. Strassen's Matrix: T(n) = 7T(n/2) + O(n²) // a=7, b=2, k=2 → log₂(7)≈2.81 > k → Case 1 → Θ(n^2.81)

// Space Complexity Examples // O(1) - Constant Space void swap(int& a, int& b) { int temp = a; // Just 1 extra variable a = b; b = temp; } // O(n) - Linear Space vector<int> copy(vector<int>& arr) { vector<int> result(arr.size()); // n elements for (int i = 0; i < arr.size(); i++) { result[i] = arr[i]; } return result; } // O(n) - Recursion Call Stack int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); // n stack frames! } // O(1) vs O(n) - Same problem, different space // Fibonacci O(n) space int fibRecursive(int n) { // O(n) stack space if (n <= 1) return n; return fibRecursive(n-1) + fibRecursive(n-2); } // Fibonacci O(1) space ✅ Better! int fibIterative(int n) { int a = 0, b = 1; // Only 2 variables for (int i = 2; i <= n; i++) { int temp = a + b; a = b; b = temp; } return b; }

Time & Space Complexity

Quick Complexity Reference

What is Time Complexity?

Understanding Growth Rates

Why We Need It:

Essential Rules:

Quick Growth Benchmarks:

Asymptotic Notations

Asymptotic Notations

1. Big O (O) — Upper Bound (Worst Case)

2. Big Omega (Ω) — Lower Bound (Best Case)

3. Big Theta (Θ) — Tight Bound (Average Case)

Case Study: Linear Search

Common Time Complexities

Time Complexity Hierarchy

How to Calculate Time Complexity

Steps to Calculate Complexity

Rule 1: Drop the Constants

Rule 2: Keep the Dominant Term

Rule 3: Keep Different Inputs Separate

Rule 4: Trace the Loop Traversal

Rule 5: Calculate Recursive depth

Master Theorem

The Master Theorem

Understanding the Variables:

The Three Canonical Cases:

Real-World Examples:

Space Complexity

Space Complexity

Key Distinctions:

Standard Space Benchmarks:

The Memory-Time Tradeoff:

Time & Space Complexity

Quick Complexity Reference

What is Time Complexity?

Understanding Growth Rates

Why We Need It:

Essential Rules:

Quick Growth Benchmarks:

Asymptotic Notations

Asymptotic Notations

1. Big O (O) — Upper Bound (Worst Case)

2. Big Omega (Ω) — Lower Bound (Best Case)

3. Big Theta (Θ) — Tight Bound (Average Case)

Case Study: Linear Search

Common Time Complexities

Time Complexity Hierarchy

How to Calculate Time Complexity

Steps to Calculate Complexity

Rule 1: Drop the Constants

Rule 2: Keep the Dominant Term

Rule 3: Keep Different Inputs Separate

Rule 4: Trace the Loop Traversal

Rule 5: Calculate Recursive depth

Master Theorem

The Master Theorem

Understanding the Variables:

The Three Canonical Cases:

Real-World Examples:

Space Complexity

Space Complexity

Key Distinctions:

Standard Space Benchmarks:

The Memory-Time Tradeoff:

1. Big O (`O`) — Upper Bound (Worst Case)

2. Big Omega (`Ω`) — Lower Bound (Best Case)

3. Big Theta (`Θ`) — Tight Bound (Average Case)

1. Big O (`O`) — Upper Bound (Worst Case)

2. Big Omega (`Ω`) — Lower Bound (Best Case)

3. Big Theta (`Θ`) — Tight Bound (Average Case)