CODEWITHSUNDEEP
recursionbig-o
kotoko
kotoko

Reputation: 599

Big O notation of recursion function called inside for loop

I'm trying to determine the big O complexity of several algorithms and I'm having trouble understanding how to reason about the following piece of code:

void recursiveFunc (n)
{
   for(int i = 0; i < 8; i++)
   {
       if (n < maxN)
       {
           recursiveFunc (n + 1);
       }
       else
       {
           for(int j = 0; j < 8; j++)
           {
              // do some stuff
           }
       }
   }
}

I have the idea this is an exponential since the recursive function is called inside the loop. O(8^n)? But I'm a bit lost on how to reason about it.

Upvotes: 1

Views: 1266

Answers (1)

Jan Legner
Jan Legner

Reputation: 674

Your tip is correct.

Given the code:

var maxN = 16;
var initN = 0;
var count = 0;
function recursiveFunc (n) {
    for(var i = 0; i < 8; i++) {
        if (n < maxN) {
                recursiveFunc (n + 1);
        } else {
            for(int j = 0; j < 8; j++) {
                count++;
            }
        }
    }
}
recursiveFunc(initN);

First call happens with n = 0:

8^1 calls of recursiveFunc (where n = 1)

calls with n = 1 then cause: 8^2 calls of recursiveFunc

...

calls with n = (maxN - 1) then cause: 8^maxN calls of recursiveFunc => visiting else branch, each call enters "some stuff" 64 times

First call happens with n = 2, maxN = 4:

8^1 calls of recursiveFunc (where n = 3)

calls with n = 3 then cause: 8^2 calls of recursiveFunc (where n = 4)

calls with n = 4 then visit else branch, each 64 times.

Therefore total count of entering the "some stuff" stage: 64 * (8^(maxN - initN))

O(8^n)

EDIT: You can see this in work here, just click "Run the snippet" and then hit the "Test" button. (Trying bigger maxN values may crash your browser)

function test () {

  var maxN = parseInt(document.querySelector("#nmax").value);
  var initN = parseInt(document.querySelector("#n").value);
  var count = 0;
  function recursiveFunc (n) {
    for(var i = 0; i < 8; i++) {
      if (n < maxN) {
        recursiveFunc (n + 1);
      } else {
        for(var j = 0; j < 8; j++) {
          count++;
        }
      }
    }
  }
  recursiveFunc(initN);
  document.querySelector("#expectedValue").innerHTML = 64 * (Math.pow(8, maxN - initN));// 64 * (8^(maxN - initN));
  document.querySelector("#realValue").innerHTML = count;
}
N: <input type=number id=n value=0><br>
NMAX: <input type=number id=nmax value=5><br>
<hr>
Expected value: <span id=expectedValue></span><br>
Real value: <span id=realValue></span><br>
<button onclick="test()">Test</button>

(I also assume that initN <= maxN)

Upvotes: 1

Related Questions