CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
Amin MOUTAI
Amin MOUTAI

Reputation: 23

Wondering the time complexity of an algorithm

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 ?

Upvotes: 1

Views: 180

Answers (5)

user3980558
user3980558

Reputation:

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.

Upvotes: 3

exaucae
exaucae

Reputation: 2675

Direct answer

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

enter image description here

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)

Upvotes: 3

Darth-CodeX
Darth-CodeX

Reputation: 2447

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

Upvotes: 1

Guru Stron
Guru Stron

Reputation: 143373

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.

Upvotes: 1

ksohan
ksohan

Reputation: 1203

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)

Upvotes: 3

Related Questions