Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

Question

I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could you make it faster (reduce time complexity)'.

I have worked on optimizations of algorithms too and things that immediately spring to head when I optimize is to take out as many nested loops as possible, look for sorted data, change data structures, etc.

Since algorithm optimization is a common thing I was wondering is there a defined set of steps or principles on how to approach the reduction of time complexity of algorithms? something akin to SOLID for Object-oriented programming, but for reducing time complexity.

Answer 1

Just something to remember: You said "could you make it faster (time complexity)". What counts in practice is the resources used for practical cases. Reducing the runtime by a factor ten may be extremely valuable, but doesn't reduce time complexity. It is in practice more valuable than reducing time complexity by a factor log log n.

Next thing to remember: In many cases "could you make it faster" has the valid response "Probably, but I wouldn't bother". Making it faster takes time in money. The first step is to figure out whether it's worth the effort. Especially in an interview.

One method that works very well is called "brute force and ignorance". It doesn't care about algorithms, but about making the identical code run faster. Removing all unneeded overhead. Check for cache usage and so on.

And the other method is finding better algorithms. O (n*n) can often be changed to O (n log n), which is massively better. And with really complicated algorithms, you may find some heuristics that improves it. For example, optimisation algorithms tend to work a lot better if you manage to start with a good solution that may be good enough to allow you showing that many other solutions cannot be optimal.

But general principles? No.

Answer 2

There are no defined easy steps you can follow. The principles you mentioned, like using efficient data structures or noticing patterns that can optimized are often the basis for optimizing algorithms, but the number of different techniques is large. Most of the techniques used in interview questions can be found in basic algorithms textbooks like Introduction to Algorithms.

Answer 3

A systematic approach is to start with Brute Force and then Keep thinking what is unnecessary or repeated, try to eliminate those steps... many times it's not so obvious and which is why it is considered a difficult process unless you have solved like hundreds of algorithmic problems ... which is when you clearly see what is unnecessary or repeated that can be eliminated.