What is time complexity of for loop of multiple conditions

user_16475364 0
Viewed 217

I was trying to develop a solution to decrease the time complexity of O(n^2) or O(n*m) algorithm to O(n) or O(n+m) algorithm. For example:

    let arr = [[1, 2], [1, 2, 3], [1, 2, 3, 4, 5, 6, 7, 8]];
    let x = 0;
    let len = getArrayMaxLength (arr) //Get the maximum length of a 2d array which in this example is 8.
    for (let i = 0; i < len && x < arr.length; ++i) {
        print (arr [x][(i % arr [x].length);
        if ((i + 1) % arr [x].length == 0) {
          ++x;
          if (x != arr.length) i = -1;
        }
    }

I'm having problem to determine the Big-O of this algorithm as i have never dealt with loop with multiple conditions that much. I've read this and this and still don't get quite right. From what i understand the time-complexity will be O(n+m). Where n is [arr.length] and m is [len] which is the output of a function getArrayMaxLength as described above.

So to sum things up. What is the time complexity of the algorithm? Thank you.

algorithm
2 Answers

If the body of your loop contains lots of conditionals but none of these conditionals add to the number of repetitions on the outer for-loop and they also don't do any computation that has a variable time based on some input, them you should consider the body as a constant, thus not influencing on the final big-O complexity.

Your assumption of O(m + n) is correct.

user_12664340

Note that every time the for loop reaches the end of an inner array, the counter (variable i) resets and you increase x, passing onto the next inner array. That means you go through every single element of your two-dimensional array, which the program output confirms.

Although n+m complexity may seem ok, it is actually a bad approximation. In practice, the complexity is always bigger because array lengths vary. Imagine that all the subarrays have the same length, so n = m. As you visit n elements for every of the n inner arrays, the total complexity would then be quadratic (n*n) and not linear. When you're working with big arrays this difference becomes very obvious.

In conclusion, the time complexity is O(n*m).

user_42327560
Related