CODEWITHSUNDEEP
javascriptalgorithmbig-o
cignis
cignis

Reputation: 31

Time complexity for a loop with two nested loops?

I understand that

var arr;  // This is an array of arrays 

for (i = 0; i < arr.length; i++)
{

  for(j = 0; j < arr[i].length; j++)
  {
   // Some code
  }
}

is n^2, however my code below is a double nested for loop and im just curious on what the complexity for this type of function would look like

var arr;  // This is an array of arrays


for (i = 0; i < arr.length; i++)
{

  for(j = 0; j < arr[i].length; j++)
  {
   // Some code
  }

  for(k = 0; k < arr[i].length; k++)
  {
   // Some code
  }
}

Upvotes: 1

Views: 2319

Answers (2)

Barmar
Barmar

Reputation: 782519

The complexity of consecutive pieces of code is the maximum complexity of each of them. So if you have two consecutive loops, and they're both O(n), then the complexity of both together is also O(n).

Since these two loops are nested inside an O(n) loop, the complexity of the whole thing is O(n^2). Just like the complexity of the original code.

Upvotes: 4

Jonas Wilms
Jonas Wilms

Reputation: 138537

A loop has the complexity O(n * content), a block of statement has the complexity of all its members added up O(n1 + n2 + ...). Now in your case that is

// v outer loop
//      v inner loop 1
//                v inner loop 2
O(n * ((n * 1) + (n * 1)))
= O(n * (n + n))
= O(n * 2n) // constants can be ignored
= O(n * n)
= O(n²)

Upvotes: 2

Related Questions