big-O
Flat is better than nested — The Zen of Python
1. How do you evaluate codes?
- Time efficiency: Faster? Time complexity
- Space efficiency: Less memory intensive?
- More readable ?
2. What is big-O notation?
- a fuzzy way for counting
- a big picture of the time efficiency of the code
3. How to measure the code performance using big-O?
- Assignment statements and if statements that are only executed once regardless of the size of the problem are O(1).
- A simple “for” loop from 0 to n (with no internal loops), contributes O(n) (linear complexity); a nested loop of the same type (or bounded by the first loop parameter), gives O(n^2) (quadratic complexity);
- A loop in which the controlling parameter is divided by two at each step (and which terminates when it reaches 1), gives O(log n) (logarithmic complexity);
- A “while” loop may vary depends on the actual numbers of iterations it will run ( OK. It means as same as the for loop. That is to say, for all kinds of loops, we only care about the actual number of iterations that they’ve executed before they hit the upper bond).
- A loop with a not-O(1) execution inside, simply multiplies the complexity of the body of the loop, by the number of times the loop will execute.
- When dealing with multiple statements, add them up.
Rules:
-
Constants doesn’t matter
-
O(2N) = O(N)
-
O(5) = O(500) = O(1)
-
O (17NN) = O (NN)
-
Smaller terms doesn’t matter
-
O($N^2$ +50N +10) == O($N^2$)
-
O(1) < O(log n) < O( Sqrt(n) ) < O(n) < O(n log n) < O($n^2$) < O($n^3$) < O($2^n$)
4. What are the big-O notations from these ML techniques?
- Linear: O(N)
- Sorting: O(nlogN)