Analyzing best-case run time of copy algorithm

Question

I'm at a loss as to how to calculate the best case run time - omega f(n) - for this algorithm. In particular, I don't understand how there could be a "best case" - this seems like a very straightforward algorithm. Can someone give me some hints / a general approach for solving these types of questions?

for i = 0 to n do
    for j = n to 0 do
        for k = 1 to j-i do
            print (k)

Answer 1

Have a look at this question and answers Still sort of confused about Big O notation it may help you sort out some of the confusion between worst case, best case, Big O, Big Omega, etc.

As to your specific problem, you are asked to find some (asymptotical) lower bound of the time complexity of the algorithm (you should also clarify whether you mean Big Omega or small omega).

Otherwise you are right, this problem is quite simple. You just have to think about how many times print (k) will be executed for a given n.

You can see that the first loop goes n-times. The second one also n-times.

For the third one, you see that if i = 1, then j = n-1, thus k is 1 to n-1-1 = n-2, which makes me think whether your example is correct and if there should be i-j instead.

In any case, the third loop will execute at least n/2 times. It is n/2 because you subtract j-i and j decreases while i increases so when they are n/2 the result will be 0 and then it will be negative at which point the innermost loop will not execute anymore.

Therefore print (k) will execute n*n*n/2-times which is Omega(n^3) which you can easily verify from definition.

Just beware, as @Yves points out in his answer, that this is all assuming that print(k) is done in constant time which is probably what was meant in your exercise.

In the real world, it wouldn't be true because printing the number also takes time and the time increases with log(n) if print(k) prints in base 2 or base 10 (it would be n for base 1).

Otherwise, in this case the best case is the same as the worst case. There is just one input of size n so you cannot find "some best instance" of size n and "worst instance" of size n. There is just instance of size n.

Answer 2

I do not see anything in that function that varies between different executions except for n

aside from that, as far as I can tell, there is only one case, and that is both the best case and the worst case at the same time

it's O(n³) in case you're wondering.

Answer 3

If this is a sadistic exercise, the complexity is probably Theta(n^3.Log(n)), because of the triple loop but also due to the fact that the number of digits to be printed increases with n.

Answer 4

As n the only factor in the behavior of your algorithm, best case is n being 0. One initialization, one test, and then done...

Edit: The best case describe the algorithm behavior under optimal condition. You provide us a code snippet which depend on n. What is the nbest case? n being zero.

Another example : What is the best case of performing a linear search on an array? It is either that the key match the first element or the array is empty.