Fibonacci Number

Given an integer n, find the nth Fibonacci number.

Constraints: 0 <= n <= 45

Example:

Input: 10 Output: 55

View Code

The definition of Fibonacci sequence is
F0= 0
F1 = 1
F 2 = F1 + F0
F i = F i-1 + Fi-2
How to solve this problem?

Fibonacci number for position 0 and 1 is 0 and 1 respectively. So wee need to iterate from 2 to n and add previous two Fibonacci numbers described by the following property-
F i = F i-1 + Fi-2.


big-O Analysis
My algorithm takes O(n) time.