Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

Question

Assume I have two algorithms:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

This is naturally O(n^2). Suppose I also have:

for (int i = 0; i < 100; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

This is O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

It seems that even though my second algorithm is O(n), it will take longer. Can someone expand on this? I bring it up because I often see algorithms where they will, for example, perform a sorting step first or something like that, and when determining total complexity, its just the most complex element that bounds the algorithm.

Answer 1

Asymptotic complexity (which is what both big-O and big-Theta represent) completely ignores the constant factors involved - it's only intended to give an indication of how running time will change as the size of the input gets larger.

So it's certainly possible that an Θ(n) algorithm can take longer than an Θ(n2) one for some given n - which n this will happen for will really depend on the algorithms involved - for your specific example, this will be the case for n < 100, ignoring the possibility of optimizations differing between the two.

For any two given algorithms taking Θ(n) and Θ(n2) time respectively, what you're likely to see is that either:

• The Θ(n) algorithm is slower when n is small, then the Θ(n2) one becomes slower as n increases
  (which happens if the Θ(n) one is more complex, i.e. has higher constant factors), or
• The Θ(n2) one is always slower.

Although it's certainly possible that the Θ(n) algorithm can be slower, then the Θ(n2) one, then the Θ(n) one again, and so on as n increases, until n gets very large, from which point onwards the Θ(n2) one will always be slower, although it's greatly unlikely to happen.

In slightly more mathematical terms:

Let's say the Θ(n2) algorithm takes cn2 operations for some c.

And the Θ(n) algorithm takes dn operations for some d.

This is in line with the formal definition since we can assume this holds for n greater than 0 (i.e. for all n) and that the two functions between which the running time is lies is the same.

In line with your example, if you were to say c = 1 and d = 100, then the Θ(n) algorithm would be slower until n = 100, at which point the Θ(n2) algorithm would become slower.

_{(courtesy of WolframAlpha)}.

Notation note:

Technically big-O is only an upper bound, meaning you can say an O(1) algorithm (or really any algorithm taking O(n2) or less time) takes O(n2) as well. Thus I instead used big-Theta (Θ) notation, which is just a tight bound. See the formal definitions for more information.

Big-O is often informally treated as or taught to be a tight bound, so you may already have been essentially using big-Theta without knowing it.

If we're talking about an upper bound only (as per the formal definition of big-O), that would rather be an "anything goes" situation - the O(n) one can be faster, the O(n2) one can be faster or they can take the same amount of time (asymptotically) - one usually can't make particularly meaningful conclusions with regard to comparing the big-O of algorithms, one can only say that, given a big-O of some algorithm, that that algorithm won't take any longer than that amount of time (asymptotically).

Answer 2

Yes, an O(n) algorithm can exceed an O(n²) algorithm in terms of running time. This happens when the constant factor (that we omit in the big O notation) is large. For example, in your code above, the O(n) algorithm will have a large constant factor. So, it will perform worse than an algorithm that runs in O(n²) for n < 10.

Here, n=100 is the cross-over point. So when a task can be performed in both O(n) and in O(n²) and the constant factor of the linear algorithm is more than that of a quadratic algorithm, then we tend to prefer the algorithm with the worse running time. For example, when sorting an array, we switch to insertion sort for smaller arrays, even when merge sort or quick sort run asymptotically faster. This is because insertion sort has a smaller constant factor than merge/quick sort and will run faster.

Answer 3

Big O(n) are not meant to compare relative speed of different algorithm. They are meant to measure how fast the running time increase when the size of input increase. For example,

• O(n) means that if n multiplied by 1000, then the running time is roughly multiplied by 1000.
• O(n^2) means that if n is multiplied by 1000, then the running is roughly multiplied by 1000000.

So when n is large enough, any O(n) algorithm will beat a O(n^2) algorithm. It doesn't mean that anything for a fixed n.

Answer 4

Long story short, yes, it can. The definition of O is base on the fact that O(f(x)) < O(g(x)) implies that g(x) will definitively take more time to run than f(x) given a big enough x.

For example, is a known fact that for small values merge sort is outperformed by insertion sort ( if I remember correctly, that should hold true for n smaller than 31)

Answer 5

Yes. The O() means only asymptotic complexity. The linear algorythm can be slower as the quadratic, if it has same enough large linear slowing constant (f.e. if the core of the loop is running 10-times longer, it will be slower as its quadratic version).

The O()-notation is only an extrapolation, although a quite good one.

Answer 6

The only guarantee you get is that—no matter the constant factors—for big enough n, the O(n) algorithm will spend fewer operations than the O(n^2) one.

As an example, let's count the operations in the OPs neat example. His two algoriths differ in only one line:

for (int i = 0; i < n; i++) {       (* A, the O(n*n) algorithm. *)

vs.

for (int i = 0; i < 100; i++) {     (* B, the O(n) algorithm. *)

Since the rest of his programs are the same, the difference in actual running times will be decided by these two lines.

• For n=100, both lines do 100 iterations, so A and B perform exactly the same at n=100.
• For n<100, say, n=10, A does only 10 iterations, whereas B does 100. Clearly A is faster.
• For n>100, say, n=1000. Now the loop of A does 1000 iterations, whereas, the B loop still does its fixed 100 iterations. Clearly A is slower.

Of course, how big n has to get for the O(n) algorithm to be faster depends on the constant factor. If you change the constant 100 to 1000 in B, then the cutoff also changes to 1000.