- For the most part, forget about space complexity. Time complexity is the important one. You can often trade off time for space, though, so be aware of how much you’re using.
- O(1), or constant time, is the best option: if you know the array index, great! Unfortunately, hash tables usually incur a space penalty. Beware of poor hashing.
- O(log n) is the next best option. Binary search. Not that common, though.
- O(n) is not bad, if you have a smallish set of things to iterate through. Or even if you have a largish set and chopping it down would be expensive. O(n) also can be very cache friendly, which can actually put its performance up there with cleverer algorithms. Beware of trying to improve O(n) if it’s going to be unfriendly to your cache. For this reason, and because it’s super easy to think about, O(n) is your bread and butter; to optimize O(n), most of the time go to a hash table.
- O(n log n) is usually only encountered in sorting, and is fine for a general purpose sort. But think about a radix sort for large data sets like scene objects.
- O(n²) is getting quite bad, and should only be used in the runtime when there is no alternative. AI routines are often offenders, so look at how to cut down the search space in at least one dimension.
- O(n³) is too bad for anything runtime; OK for offline processing.
- Don’t even think about anything higher order, unless it’s really necessary for your game AND you’re precomputing offline.