When I'm coding in-engine, I'm often only concerned with a fixed
n: I've already got a spacial partition limiting the number of objects receiving
render() to approximately those on screen and surrounding areas. The maximum batch size is usually pretty well-defined per-game, although it invariably is a little bit larger than you've planned.
In this case I'm not as much concerned with big-O as I am concerned with the constant factor multiplier and lower-order terms. For a function with runtime like
a*n^2 + b*n + c (which is
O(n^2)), I'm often much more concerned with reducing
a and possibly eliminating
c. A setup or teardown cost
c may become proportionally large vs. a small
However, this is not to say that big-O (or more particularly big-theta) is a great code smell indicator. See an
O(n^4) somewhere, or worse yet an
O(k^n) geometric time, and it's time to make sure you're considering other options.
I'm generally much more concerned about big-O optimality and jumping through hoops to find algorithms with lower big-O when I'm dealing with data make tools. While the number of objects in a given level/streaming area generally is well-defined, the total number of objects/art assets/configuration files/etc across an entire game may not be. It's also a lot larger number. Even running a parallel data make, we still wait on the order of a minute (I know, whine whine -- data make for consoles can take hours -- we're mostly small handheld games) to go through a
jam data-clean && jam data cycle.
To give a specific example: this got really out of hand with a background tile-streaming algorithm that streams 8x8 256-color tiles. It's useful to share streaming buffers between background "layers", and we might have up to 6 of them in a given level sharing the same buffer. The problem is that estimating the size of the buffer needed is based on the possible positions of all 6 layers -- and if they're a prime-number width/height/scroll rate, you quickly start getting into an exhaustive search -- which starts approaching
O(6^numTiles) -- which is in the "longer than the universe will be around" category in many cases. Fortunately most cases are just 2-3 layers, but even then, we're up above half an hour runtime. At the moment, we sample a very small subset of these possibilities, increasing granularity until a set amount of time has passed (or we've completed the task, which may happen for small double-layer configurations). We bump this estimate up a bit based on prior statistics of how often we've been proved wrong, and then add a bit of extra padding for good measure.
One other fun example: on a PC game a while back, the lead engineer experimented for a while with skip lists. The memory overhead ends up causing more cache effects, which adds a sort of non-constant multiplier to the whole affair -- so they're really not a good choices at all for small
n. But for larger sorted lists where searches are frequent, they provide a benefit.
(I often find that the naive algorithm is higher big-O, faster on smaller data sets, and easier to understand; the more interesting/complex ones (e.g. patricia trie) are harder for people to understand and maintain, but higher performance on larger data sets.)