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,

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).