Big O
What is Big O?
Big O is a way to measure the time and space of the algoritm corespoinding the input they are given.
Important concepts
- growth is with respect to the input
- Constants are dropped ( ignore constant )
- Worst case is usually the way we measure
Example :
So when someone says Oh of N, they mean your algorithm will grow linearily based on input.
- O(N)
- O(N^2)
- O(LOG N)
- O(N LOG N)
Trick
If the input halves at each step, its likely O(LogN) or O(NlogN)
Why do we use it? Often it will help us make decisions about what data structures and algorithms to use. Knowing how they will perform can greatly help create the best possible program out there.
Resource: