# Leetcode 509 - Fibonacci number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

1 | F(0) = 0, F(1) = 1 |

Given n, calculate F(n).

**Example1**

1 | Input: n = 2 |

**Iterative**

1 | // Time complexity: O(n) |

**Recursive**

1 | // Time complexity: O(n^2) |