[simonbw]

> At no point does it ever cost 2^n or any x^n.

That's only true if your n is referring to the number of iterations of each loop. If your n instead refers to the number of nested loops, you will indeed get a runtime of O(2^n).

Seeing as in this context we were talking about varying the number of nested loops, it makes sense that we would define our variable n = number of nested loops.