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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
1  
Rule 3 from Rob Pike, as cited in The Art of Unix Programming: "Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy." This is because of the difference between theoretical complexity and practical efficiency, which is ably defined in the answers below. – Wildcard Mar 21 at 3:49
    
@Wildcard That seems like a good rule of thumb. Benchmarking several contender algorithms would be even better. – G. Bach Mar 21 at 12:47
    
@Wildcard Very interesting quote. It is always interesting to think about the complexity when you're designing/implementing procedures but I usually don't break my head over them untill the procedure in question seems to be a bottleneck. – Auberon Mar 21 at 16:18
up vote 7 down vote accepted

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.

share|cite|improve this answer
1  
An $O(\log n)$ isn't always faster than an $O(n)$ one. It depends on the value of $n$ and on the hidden constants. A case in point is fast matrix multiplication, which isn't fast at all in practice. – Yuval Filmus Mar 21 at 0:07
    
That's why I added: If n is sufficiently large. In the case you mention, if the matrices grow sufficiently large, $O(log(n))$ WILL be faster, by definition – Auberon Mar 21 at 0:09
    
Isn't everything you're saying already in my answer? – Auberon Mar 21 at 0:11
7  
The OP asks about the difference between theory and practice, and you're ignoring that. Asymptotic notation is usually, but not always, useful in practice. Improving the running time fourfold can make a huge difference in practice, but asymptotic notation is completely oblivious to it. – Yuval Filmus Mar 21 at 0:14

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.

share|cite|improve this answer

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)$.

share|cite|improve this answer

Your Answer

 
discard

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

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