CODEWITHSUNDEEP
javaarraystimecomplexity-theory
Kiara Mutschler
Kiara Mutschler

Reputation: 1

What is time complexity for a nested for loop where the inner loop is for a different array?

If we are measuring time complexity for one array can we disregard a different array in our time complexity calculation? (ie. if we only care about the outer array's growth could I say O(N) or do I have to give time complexity overall O(N*M).

for (int i = 0; i <= n.size(); ++i) {

   // codes inside the body of outer loop

   for (int j = 0; j <= m.size(); ++j) {
      // codes inside the body of both outer and inner loop
   }
}

Upvotes: 0

Views: 867

Answers (2)

Giorgi Tsiklauri
Giorgi Tsiklauri

Reputation: 11110

If we are measuring time complexity for one array can we disregard a different array in our time complexity calculation?

Yes, IFF the different array is of a constant size.

If the array in question is the only one that grows proportionally to the input size n, this implies, that the other array is of a constant size, and the constant factors are disregarded in the Asymptotic Analysis. So, you will end up with O(n) time complexity.

If, however, another array is not of a constant size and it changes according to the input size, then the corresponding correlation (how it changes based on the input) should be calculated and multiplied by T=O(n).

Note, that your wording:

If we are measuring time complexity for one array

is not quite correct, as you don't calculate the Time Complexity for an array, list, or any other data structure, per se; rather you calculate it for your algorithm, which might involve different data structures, constructs, and operations.

Upvotes: 1

Bill the Lizard
Bill the Lizard

Reputation: 405735

It might be ok to ignore one loop or the other if the array size for that loop is fixed. If that's not the case, then you'd take both into account and state the complexity for the whole algorithm as O(n*m).

Upvotes: 1

Related Questions