CODEWITHSUNDEEP
complexity-theorytime-complexity
MCHAppy
MCHAppy

Reputation: 1002

Algorithm's complexity : Big O notation

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

Upvotes: 0

Views: 109

Answers (1)

chiwangc
chiwangc

Reputation: 3577

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).

Upvotes: 1

Related Questions