Why this is O(n²)
Why O(n · m), O(n²) when m ≈ n. Outer loop runs n times (n = len(haystack)). The slice + compare inside is O(m) (m = len(needle)). Worst case: needle is half of haystack, so m ≈ n, giving O(n²).
Faster algorithms. KMP and Boyer–Moore are both O(n + m). The naïve scan is what str.find uses for short needles where the constant factors of KMP don't pay off.
How to recognize quadratic complexity in the wild
O(n²) is the smell of nested for-loops both ranging over the input. Bubble sort, naive substring search, comparing every pair. The trap is that nested loops aren't always quadratic — if the inner loop is bounded by a constant, you're back to O(n).
The eight rungs of the ladder
Big-O classifies the asymptotic growth of a function, not the wall-clock time. The ladder Bugdle uses has eight rungs ordered from cheapest to most ruinous: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!). The puzzle's answer sits at rung 5 of 8. The four-guess budget plus higher/lower hints means the puzzle is solvable in at most ⌈log₂(8)⌉ = 3 perfectly-read guesses; the fourth attempt absorbs misreads of the snippet.
Common confusables
Nested loops aren't automatically quadratic — the inner loop has to range over n, not a constant. A loop that always runs ten iterations is still O(1) work per outer iteration. Similarly, a recursive function isn't automatically exponential just because it calls itself twice — if the recursion has overlapping subproblems and you memoise, you collapse back to polynomial. Always ask: what does n really mean here, and how many distinct subproblems are there?
External reference: Big O notation — Wikipedia.