VietMX Staff asked 3 years ago
Consider:
function fibs(n){
let [a, b] = [0, 1]
while (n > 0){
[a, b] = [b, a + b]
n -= 1
}
return a
}This solution is in linear O(n) time complexity, and constant O(1) space complexity. The number of loops it takes to calculate the nth fib number will still increase at a linear rate as n increases, but we are overriding the previous numbers in the sequence as we build it out, making the space complexity constant for any input n. It’s also called Iterative Top-Down Approach.
Implementation
function fibs(n){
let [a, b] = [0, 1]
while (n > 0){
[a, b] = [b, a + b]
n -= 1
}
return a
}