Time Complexity Explained

Time Complexity: The Complete Hierarchy

Every algorithm falls into a specific "class" of speed. This guide covers all 8 major types of Time Complexities, ordered from the absolute fastest to the impossible slow.

Hierarchy (Best to Worst):
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

---

1. O(1) – Constant Time FASTEST

Concept: The runtime never changes, regardless of input size.
Example: Accessing an array index or checking a dictionary key.

def check_first(arr): # Always takes 1 step. if arr[0] == 0: return "Zero" return "Not Zero"

2. O(log n) – Logarithmic Time VERY FAST

Concept: The problem size is cut in half at each step. Common in binary search and balanced trees.
Example: Finding a number in a sorted phonebook.

def binary_search(arr, target): # Input 100 -> 7 steps # Input 1,000,000 -> 20 steps while low <= high: mid = (low + high) // 2 if arr[mid] < target: low = mid + 1 else: high = mid - 1

3. O(n) – Linear Time FAST

Concept: Runtime grows directly with input. If you have 10 items, it does 10 operations.
Example: Looping through a list to find the max value.

def print_all(arr): # Runs 'n' times for item in arr: print(item)

4. O(n log n) – Linearithmic Time DECENT

Concept: Slightly slower than linear, but much faster than quadratic. This is the standard for efficient sorting algorithms (Merge Sort, Heap Sort, Quick Sort).
Analogy: Sorting a deck of cards efficiently.

def merge_sort(arr): # Uses Divide & Conquer (log n) # Plus merging the list (n) # Result: n * log n arr.sort() # Python's Timsort is O(n log n)

5. O(n²) – Quadratic Time SLOW

Concept: Growth is the square of the input. Common in algorithms with nested loops (Loop inside a loop).
Example: Bubble Sort, Insertion Sort.

def nested_loop(arr): # n * n iterations for i in arr: for j in arr: print(i, j)

6. O(n³) – Cubic Time VERY SLOW

Concept: Loop inside a loop inside a loop. Rarely used in practice except for specific mathematical operations (like simple matrix multiplication).

for i in range(n): for j in range(n): for k in range(n): print(i, j, k)

7. O(2ⁿ) – Exponential Time TERRIBLE

Concept: The operations double with every single new input. This is common in "Brute Force" recursion.
Example: Finding all subsets of a set, Recursive Fibonacci.

def fib_recursive(n): # 1 call becomes 2, then 4, then 8... if n <= 1: return n return fib(n-1) + fib(n-2)

8. O(n!) – Factorial Time IMPOSSIBLE

Concept: The absolute slowest. It grows astronomically fast. Even small inputs like n=20 can take years to process.
Example: The Traveling Salesman Problem (checking every possible route between cities).

import itertools # Permutations of a list # If list has 10 items, result is 3.6 million combinations. # If list has 20 items, computers crash. result = list(itertools.permutations(arr))

---

Summary: Which one should I use?

• ✅ O(1) & O(log n): Excellent. Aim for this.
• ✅ O(n): Good standard for processing data.
• ⚠️ O(n log n): Acceptable for sorting.
• ❌ O(n²): Avoid if n > 5,000.
• ⛔ O(2ⁿ) & O(n!): Only for very small inputs (n < 20).