Big O Notation Time Space Complexity

What is Big O Notation?

Big O Notation is a mathematical notation used to describe the upper bound of an algorithm's running time or space usage as the input size grows. It answers the question: "How does performance scale?"

Big O focuses on the worst-case scenario and describes the growth rate, not the exact number of operations. It lets you compare algorithms independently of hardware or implementation details.

Time Complexity vs Space Complexity

Type	What it measures	Example
Time Complexity	How execution time grows with input size n	Sorting n elements takes O(n log n)
Space Complexity	How memory usage grows with input size n	Storing n elements takes O(n) space

Big O Rules

Drop constants - O(2n) simplifies to O(n); constants don't matter at scale
Drop non-dominant terms - O(n^2 + n) simplifies to O(n^2); the dominant term wins
Different inputs = different variables - O(a + b) if iterating two separate arrays of size a and b
Nested loops multiply - a loop inside a loop is O(n x m), or O(n^2) if same size
Sequential steps add - two separate loops over n is O(n + n) = O(n)

Common Complexities (Fastest to Slowest)

Notation	Name	n=10	n=100	n=1000	Example
O(1)	Constant	1	1	1	Array index access, hash lookup
O(log n)	Logarithmic	3	7	10	Binary search, balanced BST
O(n)	Linear	10	100	1,000	Linear search, array traversal
O(n log n)	Linearithmic	33	664	9,966	Merge sort, heap sort
O(n^2)	Quadratic	100	10,000	1,000,000	Bubble sort, nested loops
O(2^n)	Exponential	1,024	~10^30	~10^301	Recursive Fibonacci, subsets
O(n!)	Factorial	3,628,800	~10^157	impossible	Permutations, traveling salesman brute force

Best / Average / Worst Case

In practice, we almost always care about worst case because it gives a guaranteed upper bound.

Best case (Omega) - minimum time needed (e.g., linear search finds target at index 0)
Average case (Theta - Theta) - expected time over all inputs
Worst case (O - Big O) - maximum time needed (e.g., linear search target not found)

Amortized Analysis

Amortized analysis averages the cost of operations over a sequence. A dynamic array (like C++ vector) doubles in size when full - most appends are O(1), but occasional resizes are O(n). Amortized over all operations, each append is still O(1) amortized.

O(1) vs O(n) vs O(n^2) Examples

#include <iostream>
#include <vector>
using namespace std;

// O(1) - Constant time: does NOT depend on input size
int getFirst(const vector<int>& arr) {
    return arr[0];  // always 1 operation
}

// O(n) - Linear time: grows proportionally with n
int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {  // up to n iterations
        if (arr[i] == target) return i;
    }
    return -1;
}

// O(n^2) - Quadratic time: nested loops over same input
bool hasDuplicate(const vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i + 1; j < arr.size(); j++) {  // n*(n-1)/2 comparisons
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

// O(log n) - Logarithmic: halves search space each step
int binarySearch(const vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    cout << "O(1) first: " << getFirst(arr) << endl;          // 1
    cout << "O(n) search: " << linearSearch(arr, 9) << endl;  // 4
    cout << "O(log n) bs: " << binarySearch(arr, 9) << endl;  // 4
    cout << boolalpha << "O(n^2) dup: " << hasDuplicate(arr) << endl; // false
    return 0;
}

Amortized Analysis - Java Example

public class BigOExamples {

    // O(1) - Constant time
    static int getFirst(int[] arr) {
        return arr[0];
    }

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

    // O(n^2) - Quadratic time
    static boolean hasDuplicate(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j]) return true;
            }
        }
        return false;
    }

    // O(log n) - Logarithmic time
    static int binarySearch(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        System.out.println("O(1) first: "    + getFirst(arr));          // 1
        System.out.println("O(n) search: "   + linearSearch(arr, 9));   // 4
        System.out.println("O(log n) bs: "   + binarySearch(arr, 9));   // 4
        System.out.println("O(n^2) dup: "     + hasDuplicate(arr));      // false
    }
}

Amortized Analysis - Python Example

# O(1) - Constant time
def get_first(arr):
    return arr[0]  # always 1 operation regardless of arr size

# O(n) - Linear time
def linear_search(arr, target):
    for i, x in enumerate(arr):  # up to n iterations
        if x == target:
            return i
    return -1

# O(n^2) - Quadratic time
def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):  # n*(n-1)/2 comparisons
            if arr[i] == arr[j]:
                return True
    return False

# O(log n) - Logarithmic time
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:   return mid
        elif arr[mid] < target:  lo = mid + 1
        else:                    hi = mid - 1
    return -1

arr = [1, 3, 5, 7, 9, 11, 13, 15]
print("O(1) first:",    get_first(arr))          # 1
print("O(n) search:",   linear_search(arr, 9))   # 4
print("O(log n) bs:",   binary_search(arr, 9))   # 4
print("O(n^2) dup:",     has_duplicate(arr))      # False

# O(n) duplicate check using a set - much better!
def has_duplicate_on(arr):
    seen = set()
    for x in arr:
        if x in seen: return True
        seen.add(x)
    return False

Amortized Analysis - JavaScript Example

// O(1) - Constant time
function getFirst(arr) {
    return arr[0];  // always 1 operation
}

// O(n) - Linear time
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {  // up to n iterations
        if (arr[i] === target) return i;
    }
    return -1;
}

// O(n^2) - Quadratic time
function hasDuplicate(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {  // n*(n-1)/2 comparisons
            if (arr[i] === arr[j]) return true;
        }
    }
    return false;
}

// O(log n) - Logarithmic time
function binarySearch(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log("O(1) first:",    getFirst(arr));          // 1
console.log("O(n) search:",   linearSearch(arr, 9));   // 4
console.log("O(log n) bs:",   binarySearch(arr, 9));   // 4
console.log("O(n^2) dup:",     hasDuplicate(arr));      // false

// O(n) duplicate check using a Set - much better!
const hasDuplicateOn = arr => new Set(arr).size !== arr.length;

Big trace helper

def trace_big(items):
    print('Input:', items)
    for index, value in enumerate(items):
        print(f'step={index}, value={value}, remaining={items[index+1:]}')
    return len(items)

print('operations:', trace_big([4, 1, 7, 1]))

Before you move on