A Refresher on "Big O" Notation (Python)
It’s well known that asymptotic notation is used to convey the speed and efficiency of code blocks in computer programs. I haven’t used them very much while working with Python, so I needed to refresh my memory before trying to use this great tool.
Cardinal Rule: Focus primarily the largest value in the equation of time complexity. All other factors in the time complexity equation are essentially trumped.
O(n^4+n^2+n^3+nm+100) ~= O(n^4)
Update: assuming m is linear.
Trump Rules for Time Complexity:
- Remember that we care most about the upper bound and are not so concerned with the lower (in general)
- The smaller the upper bound number the better (and consequently, faster)
- The Ladder
- Constants are less than logarithms
- Logarithms are less than polynomials
- Polynomials are less than exponentials
- Exponentials are less than factorials