Nerd Paradise : Coding Interview 5: Fibonacci

Nerd Paradise : Coding Interview 5: Fibonacci

This is one of those questions that people don't really give much thought to until they're actually in the interview. There are 4 answers to this question.

The Utterly Horrible Answer

The Fibonacci sequence can be expressed recursively:

F(1) = 1
F(2) = 1
F(n) = F(n - 1) + F(n - 2)

In fact, aside from factorial, this is one of the most common examples of a recursive function used in CS1 classes everywhere. Which is bad when you analyze the complexity. Every time you call the Fibonacci function, it will ultimately recurse down to a bunch of F(0) and F(1) calls. If you want to find the 40th Fibonacci number, that's 102,334,155. But to get to that solution, you are adding 1 to itself 102,334,155 times. The code for this is remarkably simple:

function fib(n):
    if n <= 2:
        return 1
    
    return fib(n - 1) + fib(n - 2)

If you do make the mistake of giving this as an answer and you are asked what the complexity is, it's the golden ratio to the power of n. O(1.618ⁿ)

Read full article from Nerd Paradise : Coding Interview 5: Fibonacci