# Choosing between 2 Fibonacci alternatives [closed]

• 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?

• wow, I've been downvoted the second I've posted it. – Eli Livshitz Nov 14 '19 at 18:12
• I'd believe the reason you were downvoted is because this isn't really asking for a code review, but it would be more of an opinion based answer, as you've seen yourself while searching for answers. Though I'm not the downvoter. – IEatBagels Nov 14 '19 at 18:47
• Time complexity of the Algorithm 1 is $O(2^n)$. – vnp Nov 15 '19 at 5:10

You can compute fibonacci numbers with both time and space complexity O(1).
(n) => ((Math.Pow(phi,n) - Math.Pow(1-phi, n)) / Math.Sqrt(5);

where phi is the golden ratio:
(1 + Math.Sqrt(5)) / 2