Big-Oh Notation

Question

if T(n) is O(n), then it is also correct to say T(n) is O(n2) ?

Answer 1

O also known as Big-Oh is a upper bound. We can say that there exists a C such that, for all n > N, T(n) < C g(n). Where C is a constant.

So until an unless the large co-efficient in T(n) is smaller or equal to g(n) then that statement is always valid.

Answer 2

Assuming

T(n) = O(n), n > 0

Then both of the following are true

T(n) = O(2n)
T(n) = O(n²)

This is because both 2n and n2 grow as quickly as or more quickly than just plain n. EDIT: As Philip correctly notes in the comments, even a value smaller than 1 can be the multiplier of n, since constant terms may be dropped (they become insignificant for large values of n; EDIT 2: as Oli says, all constants are insignificant per the definition of O). Thus the following is also true:

T(n) = O(0.2n)

In fact, n² grows so quickly that you can also say

T(n) = o(n²)

But not

T(n) = Θ(n²)

because the functions given provide an asymptotic upper bound, not an asymptotically tight bound.

Answer 3

if you mean O(2 * N) then yes O(n) == O(2n). The time taken is a linear function of the input data in both cases

I disagree with the other answer that says O(N) = O(N*N). It is true that the O(N) function will finish in less time than O(N*N), but the completion time is not a function of n*n so it really isnt true

I suppose the answer depends on why u r asking the question

Answer 4

Yes; because O(n) is a subset of O(n^2).