如何确定JS递归函数的复杂度？

Question

我有代码1

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);

和代码2

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);

第一个代码显示

5050
Execution time: 6

第二

5050
Execution time: 7

据我了解，code1 是线性的，所以 O(n) 和 code2 是 O(2^n)。为什么执行时间差这么小？

Answer 1

算术计算不增加复杂度，代码1是O(n) 代码2是O(1)

你的测试还不够尝试 sumTo(10000000000000000000)

Read the wiki

如何确定JS递归函数的复杂度？

How to determine complexity of JS recursive functions?

javascript

recursion

big-o