Choosing between 2 Fibonacci alternatives [closed]

Question

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

Answer 1

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

But if you needed to iterate fibonacci numbers one after the other, I would use an "iterator", then every other number would also be generated in O(1) and it would be better then the double formula.