CODEWITHSUNDEEP
loopscomplexity-theory
F.P
F.P

Reputation: 17831

Calculate amount of iterations

How can I calculate how many iterations will be done by these loops for any given N (>= 1)

for (1 <= k <= N)
    for (0 <= i < 6)
        for (0 <= j < k)
            ...

I'm especially having problems of how to deal with the innermost loop, because it depends on the value of the outermost loop. Basicall, it will be something like N * 6 * ???, but I can't figure out what ??? should be

Upvotes: 0

Views: 167

Answers (2)

avector
avector

Reputation: 398

??? should be (N+1)/2, the sum on positive integers up to N. Just to make sure I wrote a powershell script to check that theory:

for($N=1; $N -le 10; $N++)
{
  $totalCount = 0

  for ($k=1; $k -le $N; $k++)
  {
    for ($i=0; $i -lt 6; $i++)
    {
      for ($j=0; $j -lt $k; $j++)
      {    
        $totalCount++
      }
    }
  }

  Write-Host("Total Count for N={0} is {1}" -f $N, $totalCount)
  $calcTotal = ($N*($N+1)/2)*6
  Write-Host("Calulated total ={0}" -f $calcTotal)
}

Which yields:

Total Count for N=1 is 6
Calulated total =6
Total Count for N=2 is 18
Calulated total =18
Total Count for N=3 is 36
Calulated total =36
Total Count for N=4 is 60
Calulated total =60
Total Count for N=5 is 90
Calulated total =90
Total Count for N=6 is 126
Calulated total =126
Total Count for N=7 is 168
Calulated total =168
Total Count for N=8 is 216
Calulated total =216
Total Count for N=9 is 270
Calulated total =270
Total Count for N=10 is 330
Calulated total =330

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55589

Without changing how many times the internal loop is executed (though you will change the order), you can change the loops to: (this can be done since i and j are independent of each other)

for (1 <= k <= N)
  for (0 <= j < k)
    for (0 <= i < 6)

Ignoring i for the moment, we have:

k             1  2    3     ... N
j             0  0 1  0 1 2     0 1 2 ... N-1
              -  ---  -----     -------------
executions    1   2     3             N

That is, 1 + 2 + 3 + ... + N = N(N+1)/2 executions (that's a well-known formula worth knowing for these types of calculations).

Adding i simply increases this by a factor of 6, so we have 3*N(N+1).

Upvotes: 2

Related Questions