0
\$\begingroup\$
  • 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?

\$\endgroup\$
  • \$\begingroup\$ wow, I've been downvoted the second I've posted it. \$\endgroup\$ – Eli 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
2
\$\begingroup\$

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.

\$\endgroup\$

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