CODEWITHSUNDEEP
javascriptfor-looptime-complexity
piyush sanadhya
piyush sanadhya

Reputation: 464

what is time complexity of 2 for loop written in one loop

Hi i was just thinking if i write for loop like given below , what will be time complexity of it. it will o(n^2) or just o(n)

for(var i=0,j=0;i<arr1.length || j<arr2.length;i++,j++)
{
    //some code here
}

Upvotes: 2

Views: 143

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476584

The time complexity is O(max(m, n)) with m and n the size of arr1 and arr2 respectively.

In your for loop you increment both i and j after a loop. The for loop stops if both i >= arr1.length and j >= arr2.length. Since i and j always have the same value (except for the moment between increment i and j), it thus ends if both i and j have reached the end of their corresponding list.

We here make the assumption that incrementing i and j runs in constant time (well for very large numbers, that will take O(b) with b the number of bits of a number with arbitrary size), and that the body of the for loop only contains instructions that run in constant time as well.

Upvotes: 6

CertainPerformance
CertainPerformance

Reputation: 370699

Assuming there are no further loops in the //some code here, the time complexity is O(N), because the loop breaks as soon as both i<arr1.length and j<arr2.length, and both i and j are incremented on every iteration. It will run for Math.max(arr1.length, arr2.length) iterations.

For

i<arr1.length || j<arr2.length

to be false (and hence no more iterations), there needs to be

i >= arr1.length
// and
j >= arr2.length

Upvotes: 5

Related Questions