Why this is O(2ⁿ)
Why O(2ⁿ · n) (dominated by 2ⁿ). This is bitmask dynamic programming for the Travelling Salesman Problem — there are 2ⁿ subset states × n positions, and each transition is O(n). The dominant term is exponential in the number of cities.
Why not O(n!). A naive permutation enumeration *is* O(n!), but bitmask DP with memoisation (not shown here for brevity) caches sub-problems and drops to 2ⁿ. This snippet shows the DP shape without the memo dict — the rate-determining step is still the 2ⁿ subset enumeration.
How to recognize exponential complexity in the wild
O(2ⁿ) is the cost of exploring every subset or every yes/no branch without pruning. Naive recursive Fibonacci, brute-force subset-sum, generating the power set.
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 7 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.