CODEWITHSUNDEEP
javascriptalgorithmloopstime-complexitybig-o
Un Jin Jang
Un Jin Jang

Reputation: 55

What is the time complexity of this function? (nested for loop)

I think it's O(n * m) but also think its O(n)

Can't really tell which one is correct..

Considering first loop only loops 20 times (fixed amount), and second nested for loop only loops number / 20, and lastly third nested loops 3 times.

So it comes out as O(n * m / 20 * 3) which we can call it as O(n * m * k)? is this correct?

or it's O(n) because the second loops time complexity will only effect it since it's different depending on what the user inputs as number.

function loop(number) {
  let answer = 0;

  for (let i = 0; i < 20; i++) {
    for (let j = 0; j < number / 20; j++) {
      for (let k = 0; k < 3; k++) {
        answer++;
      }
    }
  }

  return answer;
}

Upvotes: 0

Views: 126

Answers (1)

Nicholas Tower
Nicholas Tower

Reputation: 85221

The outer loop always loops exactly 20 times, the inner loop always loops exactly 3 times. The only one that has any variability is the middle loop, which loops number / 20 times. So you will be incrementing answer 20 * 3 * (number / 20) times, and since constants are ignored for Big O notation, this works out to O(number).

Upvotes: 3

Related Questions