CODEWITHSUNDEEP
javascriptrecursionbig-o
Richard Rublev
Richard Rublev

Reputation: 8164

How to determine complexity of JS recursive functions?

I have code1

var start = new Date().getTime();
function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

console.log(sumTo(100));
var end = new Date().getTime();
var time = end - start;
console.log('Execution time: ' + time);

and code2

var start = new Date().getTime();
function sumTo(n) {
  return n * (n + 1) / 2;
}

console.log(sumTo(100));
var end = new Date().getTime();
var time = end - start;
console.log('Execution time: ' + time);

First code shows

5050
Execution time: 6

Second

5050
Execution time: 7

As I understand,code1 is linear,so O(n) and code2 is O(2^n). Why is execution time difference so small?

Upvotes: 0

Views: 70

Answers (1)

arslan2012
arslan2012

Reputation: 1028

Arithmetic calculations does not contribute to complexity, code 1 is O(n) code 2 is O(1)

and your test is not enough try sumTo(10000000000000000000)

Read the wiki

Upvotes: 4

Related Questions