Time Complexity — Fastest to Slowest (With Detailed Examples)

This section explains each time complexity in detail, arranged from fastest to slowest, with practical examples.

O(1) — Constant Time

Meaning: Execution time does not change with the size of the input.

Examples:

• Accessing an element in an array: arr[5]
• Inserting or removing from a stack
• Hash map lookup

O(log n) — Logarithmic Time

Meaning: The input size reduces by half each step.

Examples:

• Binary Search in a sorted array
• Binary Search Tree operations (balanced)
• Finding an item in a phonebook by halving

O(n) — Linear Time

Meaning: Time grows directly with the input size.

Examples:

• Looping through an array
• Finding max/min in a list
• Counting frequency of elements

O(n log n) — Linearithmic Time

Meaning: A combination of linear work and logarithmic splitting.

Examples:

• Merge Sort
• Quick Sort (average case)
• Heap Sort

O(n²) — Quadratic Time

Meaning: Operations inside nested loops over the same n items.

Examples:

• Bubble Sort
• Insertion Sort (worst case)
• Checking all pairs in an array

O(2ⁿ) — Exponential Time

Meaning: The algorithm doubles work with every increase in input size.

Examples:

• Subset generation (Power Set)
• Recursive Fibonacci without DP
• Solving NP problems with brute force

O(n!) — Factorial Time

Meaning: Used in problems where we generate all permutations.

Examples:

• Generating all permutations of a list
• Traveling Salesman Problem brute force

Code Examples

O(1) Example

// Access array element
int x = arr[5];

O(log n) Example

// Binary Search
int binarySearch(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

O(n) Example

// Find maximum
int findMax(int[] arr) {
    int max = arr[0];
    for (int x : arr) {
        if (x > max) max = x;
    }
    return max;
}

O(n log n) Example

// Merge Sort (simplified)
void mergeSort(int[] arr) {
    if (arr.length < 2) return;
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    mergeSort(left);
    mergeSort(right);
    merge(arr, left, right);
}

O(n²) Example

// Bubble Sort
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
    }
}

O(2ⁿ) Example

// Subset Generation
void subset(String s, String curr, int index) {
    if (index == s.length()) {
        System.out.println(curr);
        return;
    }
    subset(s, curr + s.charAt(index), index + 1);
    subset(s, curr, index + 1);
}

O(n!) Example

// Permutations
void permute(String s, String ans) {
    if (s.length() == 0) {
        System.out.println(ans);
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        String ros = s.substring(0, i) + s.substring(i + 1);
        permute(ros, ans + ch);
    }
}

Code Examples

O(1) Example

// Access array element
int x = arr[5];

O(log n) Example

// Binary Search
int binarySearch(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

O(n) Example

// Find maximum element
int findMax(int[] arr) {
    int max = arr[0];
    for (int x : arr) {
        if (x > max) max = x;
    }
    return max;
}

O(n log n) Example

// Merge Sort (simplified)
void mergeSort(int[] arr) {
    if (arr.length < 2) return;
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    mergeSort(left);
    mergeSort(right);
    merge(arr, left, right);
}

O(n²) Example

// Bubble Sort
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

O(2ⁿ) Example

// Subset generation
void subset(String s, String curr, int index) {
    if (index == s.length()) {
        System.out.println(curr);
        return;
    }
    subset(s, curr + s.charAt(index), index + 1);
    subset(s, curr, index + 1);
}

O(n!) Example

// Permutations
void permute(String s, String ans) {
    if (s.length() == 0) {
        System.out.println(ans);
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        String ros = s.substring(0, i) + s.substring(i + 1);
        permute(ros, ans + ch);
    }
}

Space Complexity — How to Calculate It

Space Complexity measures how much extra memory an algorithm needs relative to the input size n. It includes:

• Input space — memory to store the input
• Auxiliary space — extra memory your algorithm uses (variables, arrays, recursion stack)

To calculate space complexity, analyze:

1. How many variables are used?
2. Do you allocate new arrays/lists?
3. Does recursion add stack frames?
4. Does memory grow based on input size n?

O(1) Space Complexity

Constant space — memory does not grow with input size.

function findMax(arr):
    maxVal = arr[0]     # Only one variable → constant space
    for i from 1 to n:
        if arr[i] > maxVal:
            maxVal = arr[i]
    return maxVal
    

Only one variable → O(1).

O(n) Space Complexity

Memory grows linearly with input.

function copyArray(arr):
    newArr = new array of size n   # Allocating n space
    for i from 0 to n-1:
        newArr[i] = arr[i]
    return newArr
    

Creates a new array of size n → O(n).

O(n²) Space Complexity

Memory grows in two dimensions (matrix, grid).

function createMatrix(n):
    matrix = new 2D array[n][n]   # n * n memory
    return matrix
    

2D structure → O(n²).

O(log n) Space Complexity

Usually comes from recursion depth (binary search, tree operations).

function binarySearch(arr, left, right, target):
    if left > right:
        return -1

    mid = (left + right) / 2

    if arr[mid] == target:
        return mid
    else if target < arr[mid]:
        return binarySearch(arr, left, mid - 1, target)
    else:
        return binarySearch(arr, mid + 1, right, target)
    

Recursion tree height = log n → O(log n) space.

O(n log n) Space Complexity

Common in divide & conquer algorithms (e.g., Merge Sort).

function mergeSort(arr):
    if arr size <= 1:
        return arr
    
    mid = n/2
    left = mergeSort(arr[0...mid])
    right = mergeSort(arr[mid+1...n])

    return merge(left, right)   # uses extra O(n)
    

Recursion depth = log n Extra array each level = n Total → O(n log n)

O(n³) Space Complexity

Rare, typically 3D matrices.

matrix = new 3D array[n][n][n]
    

Memory grows in three dimensions → O(n³).