1
$\begingroup$

I am trying to understand the correct application of Big O notation to polynomial expressions, including terms with negative coefficients. For example, consider the polynomial $2n^3-2n^2+n+1$, where $n$ is a positive number. When emphasizing the coefficient of the leading term and using Big O notation for the remainder, can this expression be written as: $2n^3 - O(n^2)$? I am unsure if this notation is permissible in scientific writing.

Additionally, I would like to know if functions like $2n^3-2n^2+n+1$ can be written as: $2n^3+O(n)$ while ignoring the negative terms.

Any insights or guidance on this matter would be greatly appreciated.

$\endgroup$

1 Answer 1

0
$\begingroup$

Recall the definitions of various asymptotic notations.

case 1:
$f(n) = 2n^3 - 2n^2 + n + 1$ can be written as $f(n) = 2n^3 - g(n)$ where $g(n) = 2n^2 - n - 1$. Now $g(n) \in O(n^2)$ as well as $g(n) \in \Omega(n^2)$. Then you may loosely write $2n^3 - \Omega(n^2) \le f(n) \le 2n^3 - O(n^2)$. In my opinion it is better to write $f(n) = 2n^3 - \Theta(n^2)$.

case 2:
$f(n) = 2n^3 - 2n^2 + n + 1 \le 2n^3 + n$. Thus $f(n) \le 2n^3 + O(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.