CODEWITHSUNDEEP
javascriptrecursionbig-ocomplexity-theory
Misha Moroshko
Misha Moroshko

Reputation: 171321

How to calculate the complexity of a recursive function?

What's the most intuitive way to calculate the time and space complexity (Big O notation) of the following recursive function?

function count(str) {
  if (str.length <= 1) {
    return 1;
  }

  var firstTwoDigits = parseInt(str.slice(0, 2), 10);

  if (firstTwoDigits <= 26) {
    return count(str.slice(1)) +
           count(str.slice(2));
  }

  return count(str.slice(1));
}

Upvotes: 5

Views: 853

Answers (1)

gurvinder372
gurvinder372

Reputation: 68393

Apologies for my prev answer, Complexity of your code seems to be

O(2^N) or O(2^N-1) to be precise in worst case scenario.

So, If 

N = str.length ;//number of iteration

In the worst case scenario, your str consists of all N digits of either 1 or 2.

Then, If N is 20 to begin with, then it will spawn two more recursive calls of N= 18 and N = 19,

Then, N = 19 will spawn two more calls (and so one till value of N is 0 )

So, the number of calls will increase exponentially with each iteration), hence coming to the value (2^N - 1).

Upvotes: 4

Related Questions