- Task:
Return the fibonacci value at a given index.
e.g: input:6
, return:8
.
Algorithm 1:
public static fibonacci(input: number): any {
if (input <= 1) return input;
return this.fibonacci(input - 1) + this.fibonacci(input - 2);
}
Time complexity: \$O(n^2)\$,
Space complexity: \$O(1)\$
Algorithm 2:
public static fibonacci2(input: number): any {
if (input <= 1) return input;
let a = 0;
let b = 1;
let n = 0;
for (let i=2; i<=input; i++) {
n = a + b;
a = b;
b = n;
}
return n;
}
Time complexity: \$O(n)\$,
Space complexity: \$O(1)\$
Am I right regarding the complexities?
Can you suggest any alternatives that achieve the same result, with different time/space complexity?