Search code examples
javascriptcomplexity-theory

Are there any optimizations to factorial calculations?

Both the iterative and recursive versions run at linear time complexity. Are there any optimizations that can be made?

// O(n)
function factorial (n) {
  let ret = 1;
  for(let i = 2; i <= n; i++) {
    ret = ret * i;
  }
  return ret;
}

// O(n)
function factorialR (n) {
  if( n === 0 || n === 1 ) {
    return 1;
  } else {
    return n * factorialR(n - 1);
  }
}
Solution

  • Unless you are doing research, the interviewer will likely want to test the way you think.

    Showing both the iterative and recursive version with explanation of the Big O should be adequate for starters.

    If asked to optimize, qualify with a use case and suggest memoization if applicable.

    If asked to optimize with out memoization do the chicken dance.