Big-O of this algorithm?

Question

1. How can I describe the growth function in terms of n for the following algorithm?
2. What is the bounding function (the Big-O)? Is it O(n^3)?

---

for(i = 0 to n - 1)
{
    c = i + 1
    for(j = c to n)
    {
        arr[j] += arr[i];

        for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
    }
}

Answer 1

This is the rule in general :

for k nested loop you will have O(n^k) in the below case you will have O(n^3)

for(i = 0 to n - 1)
{
    c = i + 1
    for(j = c to n)
    {
        arr[j] += arr[i];

        for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
    }
}

For k loops next to each other you will have kxO(n) which comes back to O(n)

like below :

       for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
       for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }
       for(k = c to 0 step -1) // what does the keyword "step" mean?
        {
            arr[k] *= arr[j];
        }

you have O(3xn) which is O(n)

You can also read this: https://stackoverflow.com/questions/766939/finding-big-o-with-multiple-nested-loops

Answer 2

The question is about complexity but first, I was curious to know if I could compute the number of times this algorithm is doing the multiplication.

The 2 last inner loops are doing c * (n - c) iterations. This is equal to nc - c².

The very first loop make the total number of iterations: sum(c=1 to n) of (nc - c²)

sum(c=1 to n) of (nc - c²)
= n*sum(c=1 to n) of c - sum(c=1 to n) of c²
= n*(n² + n) / 2 - (2n³ + 3n² + n) / 6
= (n³ - n) / 3

So the number of iterations is (n³ - n) / 3 (answer to Q.1). And the complexity is then O(n³) (answer to Q.2).

Answer 3

I agree with the already posted answers. However, I would like to present an alternative way of obtaining an asymptotic lower bound without having to obtain the closed form.

Consider only cases of n>100. For over n/4 iterations, c is both greater than n/3 and less than 2n/3. Each of those iterations of the outer loop does at least n/3 iterations of the middle loop, each of which does at least n/3 iterations of the innermost loop. Thus the total number of innermost loop iterations is at least (n/4) * (n/3) * (n/3).

The number of innermost loop iterations is bounded above by n^3, because each of the three nested loops does no more than n iterations.

A function that is bounded below by (n^3)/36 and above by n^3 is Theta(n^3).

Answer 4

It is clearly O(n^3), since it involves three loops. And for every loop you have, upper bound of times is 'n'(even the innermost loop), because it doesn't involve constant in any loop. Hence it is n^3 solution.

I have written a dummy count program to verify the same

    int count = 0;
    for(int i = 0; i < 100; i++) {
        int c = i + 1;
        for (int j = c; j < 100; j++) {
            for(int k= c; k >= 0; k--) {
                count ++;
            }
        }
    }