Big-O

Big-O

1. N=Input or N=size of input

   • So sometimes nn is an actual number that's an input to our function, and other times nn is the number of items in an input array (or an input map, or an input object, etc.).

2. Drop Constants

   • Constants can be ignored since Big O notation is looking at what happens as n gets arbitrarily large. As n gets really big, adding 100 or dividing by 2 has a an insignificant effect.

3. Drop less significant terms

   • Only the n with higher term is kept the rest should be ignored as n gets bigger.

4. Worst Case

5. Time Vs Space

   • Usually when we talk about space complexity, we're talking about additional space, so we don't include space taken up by the inputs.

6. Beware!

   • Big O ignores constants, but sometimes the constants matter. If we have a script that takes 5 hours to run, an optimization that divides the runtime by 5 might not affect big O, but it still saves you 4 hours of waiting. Beware of premature optimization. Sometimes optimizing time or space negatively impacts readability or coding time. For a young startup it might be more important to write code that's easy to ship quickly or easy to understand later, even if this means it's less time and space efficient than it could be. But that doesn't mean startups don't care about big O analysis. A great engineer (startup or otherwise) knows how to strike the right balance between runtime, space, implementation time, maintainability, and readability.

Bilder und Dateien der Mindmap