Wondering the time complexity of an algorithm-CodePudding

In my job I had to implement an algorithm, the specifics details does not matters, but I was unable to have a clear answer about the time complexity of this specific algorithm.

In a nutshell it's look like something like that:

for(let i = 0; i < 3; i  ) {
    for(let j = 0; j < n - 1; j  ) {
        for(let k = 0; k < 8; k   {
            // Do some stuff
        }
    }
}

What is the time complexity of this algorithm ?

At the beginning I thought it would be something like O(n^3). But the more I think about, the more I think it's actually more a 0(n). Because, even though we have 3 for loop, only one can be of a variable size, the two other are constant.

So what is the actual time complexity of this algorithm ? Is it O(n^3), O(n) or even something else ?

CodePudding user response：

Yes, it would be O(n). You are right.

The total number of execution is 3 * n * 8 = 24*n where 24 can be ignored for large n. So the complexity is O(n)

CodePudding user response：

Time complexity for this code is O(n). Outer and inner loops have constant number of iterations and are independent from the input size (n). And constants are discarded for big O notation.

CodePudding user response：

Direct answer

Besides great answers already given, I'd like you to picture the calculation over each loop:

Certain implicit rules applied are relative to:

The complexity of a constant k is O(1)

example: 3 = O(1), 8 = O(1)

Given high values of a variable n and a constant k, the relation is verified: O(n k) = O(n) k = O(n)

example: O(n-1) = O(n) -1 = O(n)

Given high values of a variable n and a constant k, the relation is verified: k x O(n) = O(kn) = O(n)

example: 3x O(n) = O(3n) = O(n)

Extension

Let's change your loop to have case where you'd have O(n^3) as you were wondering:

for(let i = 0; i < n-1; i  ) {
    for(let j = 0; j < n - 1; j  ) {
        for(let k = 0; k < n-1; k   {
            // Do some stuff
        }
    }
}

Because each loop has a complexity of O(n), we have O(n) x O(n) x O(n) = O(n^3)

CodePudding user response：

The time complexity of the code is O(n):

As the outer loop iterates a constant number of times, for each time its inner loop iterates n - 1 times, and for each of these times, the innermost loop iterates a constant number of times.

Therefore you get 3 * (n - 1) * 8 = 24n - 24 and as constants are discarded for big-O notation, you get O(n).

That being said, the time complexity of the code can be affected by the code that runs inside of the innermost loop (i.e the // Do some stuff part). If you are only doing a constant number of operations there, the code complexity will not be affected. However, if for example, you sort an array of size n in there, then this will change the time complexity to n * nlogn.

CodePudding user response：

Time complexity will be O(n), because 3 and 8 are constants which can be ignored. Also, the second loop is going till n - 1, where 1 is also ignored. NOTE: All this ignorance of constants is when n becomes really large in value.

If inside all these loop a function is called, then the total calls to the function is n, but in precise manner total call will be

(8 * 3 * n) - ((8 * 3) - 1)

Which we ignore in big O notation.

Try this code in C:

#include <stdio.h>

size_t my_calls = 1;

void call_me(void){
    my_calls  = 1;
}

int main(void)
{
    size_t n = 1000; // let n = 1000

    for(size_t i = 0; i < 3; i  ) 
    {
        for(size_t j = 0; j < n - 1; j  ) 
        {
            for(size_t k = 0; k < 8; k  ) 
            {
                call_me();
            }
        }
    }
    printf("Total calls %lu\n", my_calls);
    if(my_calls == (8 * 3 * n ) - ((8 * 3) - 1))
        printf("GOOD\n");
    else
        printf("BAD\n");
    return 0;
}

LIVE DEMO