Time Complexity of an Algorithm

 

Time Complexity	Description	Example
O(1)	Constant time	Accessing an element in an array
O(log n)	Logarithmic time	Binary search
O(n)	Linear time	Iterating over an array
O(n log n)	Linearithmic time	Merge sort, quicksort (avg case)
O(n²)	Quadratic time	Nested loops over array
O(2ⁿ)	Exponential time	Recursive Fibonacci
O(n!)	Factorial time	Permutations / Travelling Salesman

O(1) - Constant Time - The time doesn't change no matter how big the input is

Ex: Accessing element of an array . int x = nums[0];  // Always takes the same time

O(log n) - Logarithimic Time : You reduce the input size by half each step i.e Guessing a number between 1 and 100 by halving the range each time

Ex: Binary Search 

 while (low <= high) {

    int mid = (low + high) / 2;

    if (nums[mid] == target) return mid;

    else if (nums[mid] < target) low = mid + 1;

    else high = mid - 1;

}

O(n) - Linear time - Time grows directly with input size

Ex : Looping over an array i.e. Reading every page in a book once

for (int i : nums) {

    System.out.println(i);

}

O(n log n) - Linearithmic Time - A combination of linear and logarithimic Time - common in efficient sorting

Ex; Merge Sort, quick sort (average case) - merge sort splits the array ( log n) and merges each part (O (n))

Sorting a phone book - split , sort and merge

O(n2) - Quadratic Time - Time grows with the square of the input - often from the nested loops

Ex; Two loops over an array - i.e. comparing every student with every other student

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

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

        // O(n²)

    }

}

O(2n) - Exponential Time - Each step doubles the number of operations

Ex : Recursive fibonacci 

int fib(int n) {

    if (n <= 1) return n;

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

}

O(n!) - Factorial Time - Insanely slow for even modest input sizes — involves all permutations.

Ex : Generating all permutations - Trying every possible seating arrangement for n people.

void permute(List<Integer> nums, int index) {

    if (index == nums.size()) return;

    for (int i = index; i < nums.size(); i++) {

        Collections.swap(nums, i, index);

        permute(nums, index + 1);

        Collections.swap(nums, i, index);

    }

}