Java Question Write an efficient itnerative ie loopbased fun

Java Question: Write an efficient itnerative (i.e. loop-based) function Fibonnaci(n) that returns the nth Fibonnaci number. By definition Fibonnaci(0) is 1, Fibonnaci(1) is 1, Fibonnaci(2) is 2, Fibonnaci(3) is 3, Fibonnaci(4) is 5, and so on. Your function may only use a constant amount of memory (i.e. no auxiliary array). Argue that the running time of the function is theta(n), i.e. the function is linear in n.

Is recursion efficient? from what I believe, it isn\'t.

Solution

Fibonacci series :0 1 1 2 3 5 8 13 21..so on.

We can build this series in Jva program and the code is shown below.

import java.util.Scanner;
public class Fibonacci
{
   public static void main(String args[])
   {
       Scanner sc=new Scanner(System.in);
       System.out.println(\"Enter size of the series..\");
       int size=sc.nextInt();
       long fib[]=new long[size];
       fib[0]=0;
       fib[1]=1;
       for(int i=2;i<size;i++)
       {
           fib[i]=fib[i-1]+fib[i-2];
       }
       System.out.println(\"Fibonacci Series upto \"+size+\" is\");
       for(int i=0;i<size;i++)
       System.out.print(fib[i]+\" \");
       System.out.println();
   }
}