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

  • \$\begingroup\$ wow, I've been downvoted the second I've posted it. \$\endgroup\$ – Elya Livshitz Nov 14 '19 at 18:12
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – IEatBagels Nov 14 '19 at 18:47
  • 1
    \$\begingroup\$ Time complexity of the Algorithm 1 is \$O(2^n)\$. \$\endgroup\$ – 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

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.