You raise a good point, but O(1) is a much better punch line.

It's definitely more stark, but O(N) would have gotten a chuckle from the intended audience and a nod to Randall for getting his complexity right.

But I'm just advocating for the devil...

Well, just to argue against my original point, the scaling of the travelling salesman problem usually applies to the time taken to figure out the optimal route, not the time taken to actually traverse it, which is O(N). If you're just looking at the route-planning stage, then the "sod it, I'll just sell on eBay" algorithm is indeed O(1).