Big O Notation of an expression

Question

If I have an algorithm that takes 4n^2 + 7n moves to accomplish, what is its O? O(4n^2)? O(n^2)?

I know that 7n is cut off, but I don't know if I should keep the n^2 coefficient or not.

Thanks

Answer 1

Everyone reading or writing about complexity of algorithms should know exactly what the Landau Symbols and asymptotic notations are, otherwise they don't really understand what is going on, or simply have an approximate (and often misleading) idea.

To simplify (a lot), let f and g be two functions f : N -> N and g : N -> N. We say that f is O(g) if and only if there's a constant M > 0 such that |f(n)| < M|g(n)|, for all n > M. That is, more informally, starting from a big value of n, all the values f(n) are smaller than a multiple of g(n) (ie, g grows faster than f).

That definition is equivalent to

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

So, let's take f(n) = 4n^2 + 7n and g(n) = n^2, and try to prove f is O(g) (I will omit {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

This implies that there is a M such that n > M ==> |f(n)| < M|g(n)|, and thus f is O(g).

So technically it is correct to say 4n^2 + 7n is O(4n^2), as it is correct to say 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), and so on. But to be meaningful, we are interested in the lower bound. So if f is O(e^n) and f is O(n^2), we are more interested into knowing that f is O(n^2), since this is much more restrictive.

VERY IMPORTANT note

What is extremelly important when choosing an algorithm is to understand that big-O notations refers to asymptotic cases, that is, when you consider extremely, unimaginable huge inputs, that can go well beyond the computational power available in the known universe (ie, infinite input sets, expressed mathematically by {n -> +oo}).

For practical uses (ie, not so huge inputs), when choosing an algorithm, sure, you will observe candidate algorithms big-O notations, but you must be sure that the chosen algorithm is well adapted (and performs better) for your (expected) input.

Finally, usually better performing algorithms are more difficult to understand and to implement properly. You must consider this fact as well when choosing an algorithm (ie, is the time I will spend debugging and fixing my implementation of this algorithm considerably superior to the time I would have to wait with another algorithm, with a worse big-O notation?. If so, you should consider the simpler, less efficient algorithm, as the overall solution would be more efficient).

Answer 2

A statement like

4n² + 7n = O(n²)

means that for some constant multiplier c, the expression cn² will eventually overtake 4n² + 7n. It's technically not incorrect to leave the coefficient in there — O(n²) and O(4n²) mean the exact same thing, because any constant c for the former can be replaced by c/4 for the latter. However, such a thing is less clear, possibly misleading, and definitely nonstandard.

Answer 3

It's O(n^2). Constant factors "move into the O". You only keep the largest exponent since this is the one dominating. And you can leave out coefficients since when comparing different algorithms even very large coefficients result in smaller total numbers than having a larger exponent (with n large enough).

Answer 4

The coefficients aren't relevant in Big O notation, so it's just O(n²). As Wikipedia explains:

[...] the coefficients become irrelevant if we compare to any other order of expression, such as an expression containing a term n³ or n².

Answer 5

Mathematically speaking, you would write O(4n²). It means that the complexity function of your algorithms behaves as n->4n² towards positive infinite.

But in computer science/algorithm, you would only write O(n²), which is sufficient to categorize your algorithm.

Answer 6

You should drop any coefficients because the question is really asking "on the order of", which tries to characterize it as linear, exponential, logarithmic, etc... That is, when n is very large, the coefficient is of little importance.

This also explains why you drop the +7n, because when n is very large, that term has relatively little significance to the final answer. If you are familiar with calculus, you might say lim n->inf(4*n^2+7n) ~= lim n->inf(4*n^2) ~= lim n->inf(n^2)

You can also think about this in a graphical sense... that is, if you graph the function 4n^2 + 7n for larger and larger values of n, a mathematician might say "it looks like n^2". Granted, it would have to be a fairly liberal mathematician, as this isn't a rigorous statement, but that's basically what O(...) is trying to convey.