We have f(n)=O[g(n)].
How to Read:
You should read equals like "is". Is means that everything over here is something over there.
Definition / Explanation:
This means that there are some suitable constants c and n0, such that f is bounded by cg(n) for all sufficiently large n. So, this is pretty intuitive notion. We have seen it before.
f(n)=O[g(n)] means there are constants c and n0,
For all n>=n0
O() notation focuses on the largest term and ignores constants -
- Largest term will dominate eventually for large enough n. -
- Constants depend on “irrelevant” things like machine speed, architecture, etc.
We are going to assume that f(n) is non-negative here. And I just want f(n) to be bounded above by g(n).
We have seen a bunch of examples, but something like 2n^2=O(n^3) defined.
And roughly this means if you drop leading constants and low order terms then this is less than or equal to that.
So, big O corresponds roughly to less than or equal to.
Used to find the upper bound of complexity or execution time.
big O is great for expressing upper bounds.