Choosing between 2 Fibonacci alternatives 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 &lt;= 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 &lt;= 1) return input;

    let a = 0;
    let b = 1;
    let n = 0;
    for (let i=2; i&lt;=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?
You can compute fibonacci numbers with both time and space complexity O(1).

(n) =&gt; ((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.