Fibonacci

Compute the nth fibonacci number.

Exercise

• Design and implement a method to compute the nth fibonacci number in the series starting with 0. n is the input parameter to the method.
• Explain the time and space complexity of your method in the comments above the method.
• Fibonacci series starting with 0 looks like this: 0 1 1 2 3 5 8 13 21 34 55 89 144 ...
• The next number in the series is the sum of the previous two numbers in the series.
• For example:
  • The 0th fibonacci number is 0
  • The 1st fibonacci number is 1
  • The 6th fibonacci number is 8

Further reading: Learn more on Fibonacci.