One way of reducing asymptotic complexity is by taking advantage of algebraic properties of the problem you're solving. For example:
- Given a collection of floating-point numbers, how do you find the one whose value is closest to a given number X? If you're doing many lookups on the same collection, then sorting the collection helps. Sorting exploits the ordering of reals: if X > Y and Y > Z, then we know that Y is a better match than Z, without even comparing X to Z. Binary search exploits this property to find a match in O(log(N)) time instead of O(N).
- How do you compute N to the fourth power, for large integer N? You can multiply three times: N * N * N * N. Because multiplication is associative, you can refactor this as (N * N) * (N * N). This takes only two multiplications: compute (N * N) once, then multiply by itself. Binary exponentiation generalizes this reassociation technique to arbitrary powers.
The algebraic properties in these cases are ordering and associativity. These examples involve numeric properties, but the approach isn't limited to numbers. Anyway, I think that just hunting for properties you can use is helpful when you're working on a piece of code, even if you end up taking a solution from korona's list.