The difference between theoretical complexity and practical efficiency

Question

If I have this pseudocode:

for i=0 to n/2 do
   for j=0 to n/2 do 
       ... do anything ....

The number of iterations is $n^2/4$.

What is the complexity of this program? Is it $O(n^2)$?

What is the intuition formal/informal for which is that complexity?

Next, if i have this other pseudocode :

for i=0 to n do
   for j=0 to n do 
       ... do anything ....

The complexity is again $O(n^2)$ -- is that correct?

Is there any difference between efficiency in practice and theoretical complexity in this case? Is one of these faster than the other?

Answer 1

Big O Formally

$O(f(n)) = \{g(n) | \exists c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) \leq c*f(n)\}$

Big O Informally

$O(f(n))$ is the set of functions that grow slower (or equally fast) than $f(n)$. This means that whatever function you pick from $O(f(n))$, let's name her $g(n)$, and you pick a sufficiently large $n$, $f(n)$ will be larger than $g(n)$. Or, in even other words, $f(n)$ will eventually surpass any function in $O(f(n))$ when $n$ grows bigger. $n$ is the input size of your algorithm.

---

As an example. Let's pick $f(n) = n^2$.

We can say that $f(n) \in O(n^3)$. Note that, over time, we allowed notation abuse so almost everyone writes $f(n) = O(n^3)$ now.

Normally when we evaluate algorithms, we look at their order. This way, we can predict how the running time of the algorithm will increase when the input size ($n$) increases.

In your example, both algorithms are of order $O(n^2)$. So, their running time will increase the same way (quadratically) as $n$ increases. Your second algorithm will be four times slower than the first one, but that is something we're usually not interested in **theoretically*. Algorithms with the same order can have different factors ($c$ in the formal definition) or different lower order terms in the function that evaluates the number of steps. But usually that's because of implementation details and we're not interested in that.

If you have a algorithm that runs in $O(log(n))$ time we can safely say it will be faster than $O(n)$ [1] because $log(n) = O(n)$. No matter how bad the $O(log(n))$ algorithm is implemented, no matter how much overhead you put in the algorithm, it will always [1] be faster than the $O(n)$ algorithm. Even if the number of steps in the algorithms are $9999*log(n) = O(log(n))$ and $0.0001*n = O(n)$, the $O(log(n))$ algorithm will eventually be faster [1].

But, maybe, in your application, $n$ is always low and will never be sufficiently large enough so that the $O(log(n))$ algorithm will be faster in practice. So using the $O(n)$ algorithm will result in faster running times, despite $n = O(log(n))$

[1] if $n$ is sufficiently large.

Answer 2

Auberon provided a very good explanation of the Big O. I will try to explain what that means for you.

First of you are right. The first code example has $\frac{n^2}{4}$ iterations, but is still in the complexity class O(n^2).

Why?

The thing about complexity classes is, that we assume that doing something several times is not that bad for runtime.

Imagine a Algorithm with complexity O(2^n) running for n=3 and taking 1 second.

We could run this 10 times, and still expect an answer after about 10 seconds.

Now Imagine increasing n by 10. The Programm will take 2^10=1024 seconds.

So the computer scientists basically said: "Man, leading factors are annoying. Let's just assume n grows to infinity and compare functions there"

Which lead to the Big O.

In Practice

In Practice it is very well possible that a solution with much worse complexity runs much faster (for "small" inputs). It is easy to imagina a Programm that runs in O(n) but needs 10^10*n iterations.

It is O(n) but even an O(2^n) solution could be faster for small n.

In summary:

The Big O is a useful tool. But you still have to think about how fast your algorithm is in practice, since it only describes how much more time it will need if the input grows.

Answer 3

If I have this pseudocode:

for i=0 to n/2 do
   for j=0 to n/2 do 
       ... do anything ....

The number of iteration is $n^2/4$.

Actually, it's $(1+n/2)^2 = n^2/4 + n + 1$.

What is the complexity of this program? Is correct $O(n^2)$?

That depends entirely on what "do anything" is. For example, if "do anything" is replaced by the line

for k=0 to 2^n do {}

then the running time is $\Theta(n^22^n)$.