Big O Notation

Describes the upper bound on how an algorithm's time or space grows relative to input size n. Used to compare algorithm efficiency.

Syntax

dsa

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

Example

dsa

O(1)      - Array index access, hash table lookup
O(log n)  - Binary search, balanced BST
O(n)      - Linear scan, linked list traversal
O(n log n)- Merge sort, heap sort
O(n^2)    - Bubble sort, nested loops
O(2^n)    - Fibonacci recursive, subset generation

// Space complexity follows the same notation