From O(n²) to O(log n): My Code Sprint Journey

Ever stared at a loop that feels like it’s running forever and wondered if you could just hack your way to speed? I did, and the result was a dramatic jump from quadratic to logarithmic time. Below I’ll walk you through the whole sprint—what I started with, why it was slow, how I rewrote it, and what you can learn from my experience. Grab a coffee; this will get technical but stay witty.

1️⃣ The Problem Space

I was building a tiny search utility for a toy database of 10,000 user records. The original algorithm looked like this:

def naive_search(records, target):
  for i in range(len(records)):
    if records[i] == target:
      return i
  return -1

That’s a classic O(n) linear scan—fine for 10,000 items. But the twist? The records were unsorted, and every lookup triggered a full scan. In production, that meant:

• High CPU spikes during peak traffic.
• Unpredictable latency for end‑users.
• An inability to scale past a few thousand records without a redesign.

My goal was to bring the search time down to O(log n), which meant implementing a binary‑search‑friendly structure.

2️⃣ The Road to Insight

I started by profiling the code. cProfile revealed that 95% of runtime was spent inside the loop. That’s a sign you’re looking at an algorithmic bottleneck, not just a hot‑spot bug.

Next, I asked: What if the data were sorted? Binary search would give us O(log n). The catch? Sorting itself is O(n log n), but if the data are static or change infrequently, sorting once and reusing the sorted list is a net win.

3️⃣ The Re‑write: From O(n²) to O(log n)

Step 1: Sort Once

Instead of sorting on every call, we sort once during initialization and keep the sorted list cached.

class Searcher:
  def __init__(self, records):
    self.records = sorted(records) # O(n log n)

  def binary_search(self, target):
    left, right = 0, len(self.records) - 1
    while left <= right:
      mid = (left + right) // 2
      if self.records[mid] == target:
        return mid
      elif self.records[mid] < target:
        left = mid + 1
      else:
        right = mid - 1
    return -1

Step 2: Benchmarking

I set up a simple benchmark comparing the naive linear scan to the new binary search. The results were dramatic:

That’s a 34× speed‑up for each lookup. The initial sort cost is amortized over thousands of queries.

Step 3: Handling Updates

If the dataset changes frequently, we can maintain a balanced binary search tree (e.g., bisect module in Python) or use a database index. For the sake of this post, I used bisect.insort to keep the list sorted on insert:

import bisect

def add_record(self, record):
  bisect.insort(self.records, record)

Now each insert is O(log n), keeping the overall structure efficient.

4️⃣ Lessons Learned

1. Profile before you refactor. You saved time by focusing on the real bottleneck.
2. Think about data mutability. A static dataset is a gold mine for binary search; dynamic data requires more sophisticated structures.
3. Amortize expensive operations. One heavy sort can pay off if it’s reused many times.
4. Keep an eye on constants. Even O(log n) can be slow if the constant factors are high—use efficient libraries.

5️⃣ Takeaway: Code Sprint Checklist

• Identify the algorithmic complexity.
• Profile to confirm your hypothesis.
• Select a data structure that matches the desired complexity.
• Implement and benchmark.
• Handle edge cases (updates, deletions).

Conclusion

By swapping a linear scan for binary search and caching the sorted list, I turned an O(n) nightmare into a lightning‑fast O(log n) operation. The key was to think algorithmically, profile aggressively, and embrace data structures that make the math work for you.

Next time your code feels like it’s stuck in a traffic jam, remember: sometimes the fastest route is to sort it out. Happy coding, and may your loops stay short!