Why Writing 100 Lines of Code can be Better than just 2 - A Gentle Introduction to Time Complexity

🎯 Introduction

Have you ever played a logic puzzle game where you're given a set of objects, and one of them is slightly different — maybe heavier or lighter — and you need to find it with as few checks as possible?

Let’s take a classic example:

You have 9 balls. 8 of them are of the same weight, but 1 is either heavier or lighter. How do you find the odd one out using the least number of comparisons?

Most of us instinctively reach for a simple solution: write a for loop, compare each ball to the next, and boom — done. It’s short, easy, and works… but is it efficient?

Let’s explore how the Divide and Conquer technique makes you look like a genius with just two comparisons.

---

🔍 The Naive Approach: Simple Loop, More Comparisons

If you're a beginner, you might write something like this in code:

for (int i = 1; i < 9; i++) {
    if (balls[0] != balls[i]) {
        cout << "Found the odd one!" << endl;
        break;
    }
}

✅ Pros:

• Code is short and clean

• Easy to understand

❌ Cons:

• Can take up to 8 comparisons in the worst case

• Not scalable or optimized

Now imagine if you had 81 balls. You’d need up to 80 comparisons — not fun.

---

🧠 The Smarter Way: Divide and Conquer

Let’s apply some strategy instead of brute force. Here’s how the Divide and Conquer method works:

Step 1: Divide the Balls

Split the 9 balls into 3 groups of 3.

• Group A: Ball 1, 2, 3

• Group B: Ball 4, 5, 6

• Group C: Ball 7, 8, 9

Step 2: First Comparison

Weigh Group A vs Group B using a balance scale (or simulate it in code).

• If the scale balances ➝ the odd ball is in Group C

• If one side is heavier/lighter ➝ the odd ball is in that group

This reduces the problem to just 3 balls.

Step 3: Second Comparison

Now weigh any two balls from the suspect group (say Ball 7 vs Ball 8):

• If one is heavier or lighter ➝ you’ve found the odd one

• If they balance ➝ the third ball is odd

✅ Only 2 comparisons — regardless of where the odd ball is!

---

🧩 Real-World Analogy

Think of it like finding a fake coin among real ones using a balance scale. You don’t want to check each coin one by one like a beginner. You want to divide and isolate the problem intelligently.

This technique is often used in algorithms like:

• Binary Search

• Merge Sort

• Quick Sort
  Where the goal is to reduce the size of the problem with each step.

---

🧾 Quick Diagram

---

📘 Key Takeaways

• Divide and Conquer is a smart strategy that reduces operations by narrowing the scope.

• Don’t judge an algorithm by code length — sometimes, longer code is more optimized.

• Efficient logic like this can scale better and impress interviewers in coding challenges.

---

🚀 Call to Action

Next time you're solving a problem, resist the urge to jump into a quick loop. Step back. Ask:

“Can I break this problem into smaller parts and solve it smarter?”

Try using this trick with 27 balls and see if you can do it in just 3 comparisons! 💡