Discussion on: Big O Notation as a Mid-Level Developer Who Has Been Avoiding It Since Bootcamp: Arrays and Time Complexity

We don't always need things to be super duper fast.

Often times one may prefer an O(N log N) algorithm over an O(N) one because the code will be simpler. For example, in some cases you can avoid sorting things, but doing so will make your code 5x longer and more complex.

However, in general we want to avoid O(N^2) type stuff such as this Java code:

String s = "";
for (int i = 0; i< N; i++) {
    s += "something";
}

This sort of thing can appear in our code by mistake and can really create a lot of slow downs. And sometimes we say: "ah.. no big deal.. I'll just make it search through the list every time.. how long can that list really be?"

And bad things can happen. For example:

while (... ) :

       for x in list: 
            if x in otherList :
                 // something

Adding a line to convert otherList into a set would make this algorithm linear instead of quadratic.

Rarely, it really really does make sense to optimize it to as fast as possible. But that is generally when we're optimizing some process that takes minutes or hours, and we really want to bring that down as much as possible. Or if we're doing something realtime.

Fortunately, often you can solve things by just using a dictionary (or hash map) or a set (or hash set) to speed up your code a lot just using the datastructures your library provides.

So as a rule of thumb:

1. don't do obviously slow things (like I showed above)
2. keep your code simple (you don't have to use a heap each time or some fancy tree that will make your code too complex)
3. Use built in tools like hash maps to speed up your code
4. When it really really really matters, get super fancy but make sure you really need to go there