Big O Notation

Big O notation describes the asymptotic upper bound of a function, used to analyze algorithm time/space complexity while ignoring constants and lower-order terms.

Purpose

To abstract the asymptotic growth rate of algorithm efficiency for comparing and choosing algorithms.

Mechanism

f(n)=O(g(n)) means there exist constants C and n0 such that |f(n)|≤C|g(n)| for all n>n0. Common orders: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!). It focuses on worst-case upper bounds.

Use cases

Algorithm complexity analysis
Data structure selection
Performance optimization decisions
Interviews and teaching

Examples

Input
```
Binary search
```
Output
```
O(log n)
```
Halves each time

Common errors

Ignoring constant factors misjudges real-world performance: Big O is asymptotic; benchmark for real behavior

Related terms

Sorting Algorithm

Sorting algorithms arrange elements in order—quicksort, merge sort, and heapsort are common—with complexity ranging from O(n log n) to O(n²).

Binary search compares against the middle of a sorted array and halves the range each time, locating a target in O(log n); it is the foundational efficient search algorithm.

A hash table maps keys to a bucket array via a hash function, providing average O(1) lookup/insert/delete; it is among the most used data structures.

References