Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

What notation is used to discuss the coefficients of functions in big-O notation?

I have two functions:

  • $f(x) = 7x^2 + 4x +2$
  • $g(x) = 3x^2 + 5x +4$

Obviously, both functions are $O(x^2)$, indeed $\Theta(x^2)$, but that doesn't allow a comparison further than that. How do I discuss the the coefficients 7 and 3. Reducing the coefficient to 3 doesn't change the asymptotic complexity but it still makes a significant difference to runtime/memory usage.

Is it wrong to say that $f$ is $O(7x^2)$ and $g$ is $O(3x^2)$ ? Is there other notation that does take coefficients into consideration? Or what would be the best way to discuss this?

share|cite|improve this question

migrated from Oct 23 '13 at 2:19

This question came from our site for professional and enthusiast programmers.

It's not wrong, it's just redundant, because $O(7 x^2) = O(x^2)$. –  Oli Charlesworth Oct 7 '13 at 23:17
See also our reference question. –  Raphael Oct 28 '13 at 7:35

2 Answers 2

up vote 9 down vote accepted

Big-$O$ and big-$\Theta$ notations hide coefficients of the leading term, so if you have two functions that are both $\Theta(n^2)$ you cannot compare their absolute values without looking at the functions themselves. It's not wrong per se to say that $7x^2 + 4x + 2 = \Theta(7x^2)$, but it's not informative because $7x^2 + 4x + 2 = \Theta(3x^2)$ is also true (and, in fact, it's $\Theta(kx^2)$ for any positive constant $k$).

There are other notations you might want to use instead. For example, $\sim$ notation is a much stronger claim than big-$\Theta$:

$\qquad \displaystyle f(x) \sim g(x) \iff \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1$

For example, $7x^2 + 4x + 2 \sim 7x^2$, but the claim $7x^2 + 4x + 2 \sim 3x^2$ would be false. You can think of tilde notation as $\Theta$ notation that preserves the leading coefficients, which seems to be what you're looking for if you do care about the leading coefficient of the dominant growth term.

share|cite|improve this answer
Tilde notation is what I'm looking for. I was sure there was something I just couldn't recall what it was called and searches proved fruitless. Thanks! –  El Bee Oct 7 '13 at 23:48

The tilde is one approach. If you want to stick with $O$, you could say

$\qquad f(x) = 7x^2 + O(x)$ and

$\qquad g(x) = 3x^2 + O(x)$.

share|cite|improve this answer
Even better: say f(x) = 7x^2 + o(x^2), using little-o notation to clarify that what's left is asymptotically smaller than x^2. –  templatetypedef Oct 9 '13 at 4:06
O(x) is strictly smaller than o(x^2), so using that would be less clear than using big-O. On the other hand, using little-o is definitely more common when you want to say that you've got the right first term, because then you don't need to worry about the next term. (And if we're wanting to be completely clear, then we would need to explain why we don't just write down 7x^2+4x+2 in the first place, since it is exactly correct. –  Teepeemm Oct 9 '13 at 4:43
You're absolutely right... my apologies! –  templatetypedef Oct 9 '13 at 17:56
Note that the rigorous way of writing this would be "$f(x) = 7x^2 + g(x)$ with $g(x) \in O(x)$". In any case, this is very useful if you want to fix more than the "first" constant; you can say "$f(x) = 7x^2 + 4x + O(1)$" which you can not do with $\sim$. –  Raphael Oct 28 '13 at 7:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.