Suppose we have a function, f(n)=n+10.
We say that f(n)∈O(n), meaning O(n) represents the upper bound of the function.
It is also true that f(n)∈O(n2) or f(n)∈O(n3) and so on.
So how can we say that O(n) is the upper bound when O(n2) is comparatively bigger bound and O(n3) is much bigger bound?
Please forgive if I have understood the concept wrongly.
4
It is very easy to eliminate your confusion because it comes from a single word:
O(n) represents the upper bound of the function.
That’s incorrect. The correct statement is:
O(n) represents an upper bound of the function.
Big-O notation does not mean that the function named in the notation is the least upper bound, just that it is an upper bound.
When we rewrite your question as:
How can we say that O(n) is an upper bound when O(n2) is comparatively bigger bound and O(n3) is much bigger bound?
the question becomes clear. There are no humans taller than 100 meters tall; that’s an upper bound on human height. 200 meters and 10000000 meters are also upper bounds; the existence of larger upper bounds does not mean that a smaller upper bound is not also an upper bound. None of these are the least upper bound.
Now, in your example O(n) happens to be the least upper bound on the function you give. There are also larger upper bounds, as you note, and therefore those are not the least upper bounds.
5
f(n) = O(g(n)) states that if there exists some constant c>0 and n0>0, then f(n) <= cg(n) for all n >= n0. Here n0 is a limit above which we consider n i.e. we try to find asymptotic notation that itself means that we want to find time complexity for large values of n. So, we consider n0 as lower limit of n and above n0 this statement holds.
So, you have misunderstood that O(g(n)) with O(n), if we have two function with time complexity f(n1) = O(n1) and f(n2)= O(n22) then there is a property of Big-O which is O(resulting function) = max(O(n1),O(n22)). So, by this in this case O(n2) is upper bound in comparison to O(n).