Question:

Given a number n, give me a function that returns the nth fibonacci number. Running time, space complexity, iterative vs. recursive.

// Recusive// O(2^n)public int fibonacci(int n){  if (n <= 0)    return 0;  if (n == 1)    return 1;  if (n == 2)    return 2;  return fibonacci(n - 2) + fibonacci(n - 1);}// Iterative// O(n)public int fibonacci(int n){    if (n <= 0)        return 0;    if (n == 1)        return 1;    if (n == 2)        return 2;            // last, cur, next    int last = 1;    int cur = 2;        for (int i = 3 ; i <= n ; i ++)    {        int temp = cur;        cur = cur + last;        last = temp;    }    return cur;}