O( sqrt(n) ) = O(n) ?
We should find c and n0 verifying : 0 ( sqrt(n) ) < c*n ; c>0 and n>n0
How to find c and n0 ? or should i find another idea ?
Thanks
Add a comment
|
1 Answer
For n > 1, we have √n > 1, hence we have the following inequality:
√n < √n * √n = n, for any n > 1.
So we can take c = 1 and n0 = 2 to prove that √n = O(n).
Remark
Strictly speaking, you should avoid writing down something like O(√n) = O(n). Big-O notation is for describing the asymptotic upper bound of a function, but O(√n) is not a function.
O(√n) = O(n) is an abuse of notation, it really means the following:
If f is a function such that f(n) = O(√n), then f(n) = O(n).
In our case, if for any function f we have f(n) = O(√n), since √n < n for any n > 1, clearly we have f(n) < c * √n < c * n for any n > 1, and hence f(n) = O(n).
4 Comments
MCHAppy
You proved that sqrt(n)=O(n) , then how to prove O(sqrt(n))=O(n) ? Is there a rule like
f(n)=O(g(n)) => O(f(n))=O(g(n)) ?MCHAppy
But wait , you have proved just
f(n) = O(√n) => f(n)=O(n) , Isn't necessary to prove f(n) = O(n) => f(n)= O(√n) so that O(√n)=O(n) ? I still a little bit confused .
chiwangc
Well spot! The problem why this notation should be avoid is because
= is a reflexive relation, O(√n)=O(n) implies O(n)=O(√n), which is definitely not what we mean! (because it is completely wrong)chiwangc
You usually see something like
O(√n)=O(n) when you are deriving an asymptotic upper-bound of a function, where you see a chain of big-O equalities like f(n) = O(g(n)) = O(h(n)). But you should not write something like O(√n) = O(n) as a standalone statement.