You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Fastest Way to Calculate Fibonacci Sequence

Nicholas Wong
Nicholas Wong

Question

Construct an algorithm so that the Nth item of Fibonacci Sequence can be found in the shortest time. Definition of Fibonacci Sequence is:

 f(n) = 0 , when n = 0 
 f(n) = 1 , when n = 1 
 f(n) = f(n-1) + f(n-2), when n > 1

Solution

There are many solutions for this, the simplest way is to use recursive function.

fibonacci(n) 
    if n equals 0 then return 0 
    else if n equals 1 then return 1 
    else return fibonacci(n-1) + fibonacci(n-2)

There is another way actually, through using loops. The time complexity is O(n).

fibonacci(n) 
    if n equals 0 then return 0 
    else if n equals 1 then return 1 
    fib_n_minus_2 = 0 
    fib_n_minus_1 = 1 
    fib_n = 0 
    for i equals 2 to n 
        fib_n = fib_n_minus_1 + fib_n_minus_2 
        fib_n_minus_2 = fib_n_minus_1 
        fib_n_minus_1 = fib_n 
    return fib_n
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.