DEV Community

Cover image for 💡 TIME COMPLEXITY PRIMER – Understand Big O Like a Kid With Candies 🍬
Ankush Singh Gandhi
Ankush Singh Gandhi

Posted on

💡 TIME COMPLEXITY PRIMER – Understand Big O Like a Kid With Candies 🍬

#datastructures #algorithms #interview #python

🧠 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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

❓ What's the time complexity?

✅ Answer: 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]
Enter fullscreen mode Exit fullscreen mode

❓ Time complexity?

✅ Answer: 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)
Enter fullscreen mode Exit fullscreen mode

❓ Time complexity?

✅ Answer: 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!")
Enter fullscreen mode Exit fullscreen mode

❓ Time complexity?

✅ Answer: 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
Enter fullscreen mode Exit fullscreen mode

❓ Time complexity?

✅ Answer: O(log n) — cut the box in half each time!

✨ Challenge Yourself:

Try to guess the Big O for these:

  1. Reversing a list of n items
  2. Adding an item to a dictionary
  3. Looping twice one after the other (not nested)
  4. Creating all possible pairs in a list
  5. 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)

Top comments (0)