Download on the App StoreApp Store

Algorithm Complexity

20 cards@learner82946550

Big O notation and the time complexity of common operations and algorithms.

Open in Nooli

Free deck. Start learning right after you install.

Deck code vp4vjj3vtp

Cards

5 of 2020 of 20
O(1)
Constant time. Doesn't depend on input size. Example: accessing an array element by index.
O(log n)
Logarithmic. Input is halved at each step. Example: binary search.
O(n)
Linear. One pass over the input. Example: finding the max in an array.
O(n log n)
Linearithmic. Typical for efficient sorting. Example: merge sort, heap sort.
O(n²)
Quadratic. Usually two nested loops. Example: bubble sort, comparing all pairs.
Show 15 more cards

Or learn them all in the app
O(2ⁿ)
Exponential. Doubles with each new element. Example: generating all subsets; naive recursive Fibonacci.
O(n!)
Factorial. Grows extremely fast. Example: generating all permutations.
Hash map lookup / insert
O(1) on average, O(n) in the worst case (many collisions).
Binary search
O(log n) time. Requires a sorted array.
Linear search
O(n) time.
Merge sort
O(n log n) time in all cases, O(n) extra space. Stable.
Quicksort
O(n log n) average, O(n²) worst case. O(log n) space on average.
Append to a dynamic array
Amortized O(1). Occasionally O(n) when it resizes.
Insert at the start of an array
O(n) — all elements must shift.
Insert at the head of a linked list
O(1)
Access by index in a linked list
O(n) — you must walk from the head.
Heap: insert / extract min
O(log n). Peek at min: O(1).
BFS / DFS on a graph
O(V + E) — vertices plus edges.
Space complexity of recursion
At least O(depth) because of the call stack.
Big O vs Big Θ vs Big Ω
O — upper bound Θ — tight bound Ω — lower bound