This content originally appeared on DEV Community and was authored by Ankush Singh Gandhi
What is Time Complexity?
Think of time complexity like asking:
“How many steps will my program take as the input gets bigger?”
Imagine you’re:
Putting LEGO blocks one by one (O(n))
Checking only the first one (O(1))
Flipping every page of a big book to find a word (O(n))
Searching in a sorted drawer by cutting it in half every time (O(log n))
Big O Notation – Like Candy Boxes!
Let’s say you have n candies:
O(1) — “I take 1 candy, no matter how many I have”
def get_first(candies):
return candies[0]
No matter if you have 10 or 10,000 candies — you just grab the first one.
O(n) — “I check every candy”
def find_sour_candy(candies):
for candy in candies:
if candy == 'sour':
return True
If there are 5 candies, you may look 5 times. If there are 100? You might look 100 times!
O(n²) — “I compare every candy with every other candy”
def find_duplicates(candies):
for i in candies:
for j in candies:
if i == j and i != j:
return True
Imagine you’re checking every candy against every other candy — it gets super slow when the pile grows!
O(log n) — “I cut the candy box in half each time!”
def binary_search(candies, target):
left, right = 0, len(candies) - 1
while left <= right:
mid = (left + right) // 2
if candies[mid] == target:
return True
elif candies[mid] < target:
left = mid + 1
else:
right = mid - 1
Smart search! Cut your pile in half every time until you find the candy
O(n log n) — “Sort candies smartly!”
Merge sort, quicksort — faster than checking every pair like O(n²), but slower than O(n)
Analogy Recap:
| Big O | Like this… |
|---|---|
| O(1) | Grab the first candy  |
| O(n) | Taste every candy one by one  |
| O(n²) | Compare every candy with every other candy  |
| O(log n) | Smart guess by cutting box in half each time  |
| O(n log n) | Smart sorting like organizing Lego blocks fast  |
Exercise 1: Candy Basket
You have a basket of n candies. You want to find if there’s any red candy.
def has_red(candies):
for candy in candies:
if candy == "red":
return True
What’s the time complexity?
O(n)— you may need to check all the candies!
Exercise 2: Toy Shelf
You have a list of 10 toys. You always play with the first one.
def play_with_toy(toys):
return toys[0]
Time complexity?
O(1)— always 1 step, no matter how many toys!
Exercise 3: Checking Every Friend’s Name 
You want to say hi to every friend at the party.
def say_hi(friends):
for friend in friends:
print("Hi", friend)
Time complexity?
O(n)— say “Hi” once per friend!
Exercise 4: Double Trouble 
You want to check every pair of kids to see if they’re best friends.
def check_best_friends(kids):
for kid1 in kids:
for kid2 in kids:
if kid1 != kid2:
print(f"{kid1} and {kid2} might be besties!")
Time complexity?
O(n²)— for each kid, check with every other kid.
Exercise 5: Magic Box 
You have a sorted list of stickers. You want to find “Unicorn” using binary search.
def find_unicorn(stickers):
left, right = 0, len(stickers) - 1
while left <= right:
mid = (left + right) // 2
if stickers[mid] == "Unicorn":
return True
elif stickers[mid] < "Unicorn":
left = mid + 1
else:
right = mid - 1
Time complexity?
O(log n)— cut the box in half each time!
Challenge Yourself:
Try to guess the Big O for these:
- Reversing a list of
nitems - Adding an item to a dictionary
- Looping twice one after the other (not nested)
- Creating all possible pairs in a list
- Looping inside a loop inside a loop (3 levels!)
Big-O Time Complexities Cheat Sheet
| Category | Operation / Pattern | Time Complexity |
|---|---|---|
| Arrays | Traversal, updates | O(n) |
| Merge Sort | O(n log n) | |
| Quick Sort (average) | O(n log n) | |
| Quick Sort (worst case) | O(n²) | |
| Binary Search | O(log n) | |
| Two-pointer / Sliding Window | O(n) | |
| Prefix Sum construction | O(n) | |
| Strings | Reverse / Palindrome check | O(n) |
| Hashmap-based Anagram check | O(n) | |
| Sorting-based Anagram check | O(n log n) | |
| Linked List | Reverse (iterative / recursive) | O(n) |
| Detect Cycle (Floyd’s) | O(n) | |
| Merge Two Sorted Lists | O(n) | |
| Find Middle Node | O(n) | |
| Stack / Queue | Push / Pop / Enqueue / Dequeue | O(1) |
| Valid Parentheses | O(n) | |
| Next Greater Element (Monotonic Stack) | O(n) | |
| Hashing | Insert / Search / Delete (average) | O(1) |
| Count Frequencies | O(n) | |
| Subarray with Sum / No Repeats | O(n) | |
| Recursion / Backtracking | Subsets / Permutations | O(2^n * n) |
| Trees (Binary) | Traversals (Inorder / Pre / Post / Level) | O(n) |
| Height, LCA, Validate BST | O(n) | |
| Heaps | Insert / Delete (Min / Max heap) | O(log n) |
| Build heap (heapify array) | O(n) | |
| Dynamic Programming | 0/1 Knapsack | O(n * W) |
| Fibonacci (memoized) | O(n) | |
| Longest Common Subsequence (LCS) | O(n * m) | |
| Graphs | DFS / BFS traversal | O(V + E) |
| Detect Cycle (undirected) | O(V + E) | |
| Topological Sort | O(V + E) |
This content originally appeared on DEV Community and was authored by Ankush Singh Gandhi