why the big-oh of a linear function is n^2?

Question

I know the definitions and differences of big-theta, big-oh, and big-omega in finding time complexity of algorithms. what I can't understand is that why the big-oh of a linear function cannot be O(n).

0ドル \le an + b \le cn \Rightarrow c = a + \frac b {n_0}$

so we could find a value for constant $c$. as a result, the big-oh of a linear function can also be $n$. am I right??

Note: I have read all the previous answers and questions in this commission and others. but I didn't understand. that's why asked a new question

• user12859: What makes you think ​ "the bog-oh of a linear function cannot be O(n)" ? ​ ​ ​ ​
• David Richerby: Key point: there is no such thing as "the big-O of a function". Tom's answer gives the details.
• Raphael: You have it backwards. Functions don't "have a big-oh". Each function is a member in many sets $O(\_)$.
• Raphael: Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck!

Answer 1

A function does not have a unique big-oh. $O(f(n))$ denotes a class of functions that are big-oh of $f(n)$. Big-oh is used to give upper bounds.

For example, $f(n)=3n+5$ is $O(n),ドル but it is also $O(n^2)$ and also $O(n^3)$ and also $O(2^{2^{2^n}})$. However, $f(n)$ is (in this example) not $O(\log n)$.

In set theory notation, we have $O(n)\subset O(n^2),ドル i.e. any function that is $O(n)$ is also $O(n^2)$. However, if we had a function that is $O(n)$ and you gave $O(n^2)$ as an upper bound, that would not be incorrect, but it would be a weaker result than saying it is $O(n)$.

$\Omega$ works the other way around (i.e., it is used for lower bounds). A function that is $\Omega(n^2)$ is also $\Omega(n)$. $\Theta$ is used to give "tight" bounds: a function that is $\Theta(n^2)$ is neither $\Theta(n)$ nor $\Theta(n^3)$.

• Thumbnail: The trouble is that people use $O$ when they mean $\Theta,ドル because they think the former means the latter.