Why use Big O Notation?
To measure and compare the implementation of algorithms.
What is Big O?
Big O allows us to talk about the runtime of an algorithm as the inputs grow
What is the formal definition of Big O?
An algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n) as n increases.
Big O measures the worst case of an algorithm: the upper bound.
When is an example of O(n^2) occurs?
When a O(n) operation is nested in another O(n) operation. This isn’t O(2N) because O(2N) is when two O(N) operations occur sequentially
How to measure the complexity of a loop?
The complexity of a loop is the length of the loop times the complexity of whatever happens inside of the loop.
What are the most common Big O run times in ascending order?
O(1) -> O(long n) -> O(n) -> O(n log n) -> O(n^2)
What is time complexity?
How we analyze the runtime of an algorithm as the size of the inputs increase
What is space complexity?
How much additional memory do we need to allocate in order to run the code in our algorithm?
What are the rules of thumb for Big O time complexity?
- Arithmetic operations are constant.
2 Variable assignment is constant. - Accessing elements in an array or object is constant.
- In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop
What are the rules of thumb for Big O space complexity?
- Most primitives are constant space.
- Strings require O(n) space (where n is the string length)
- Reference types are generally O(n) where n is the length (for arrays) or the number of keys (for objects)
What is better: O(n) or O(log n)?
O(log n)
