Question

1. The (infinite) Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89… is generated by adding the last 2 elements of the series to give the next element. So, the item after 89 is 89 + 55 = 144. Write a program that generates the nth element in the Fibonacci series. The user will ask for the 10th element for example, and the program will display the 10th element.
2. 1. How long does it take for your program to find the 49th element in the series?
3. 2. What is the 49th element (where 0 is the 1st, 1 is the 2nd, 1 is the 3rd, 2 is the 4th, and so on):
4. 3. Comment on the running time for your program. What is the order?

Answer 1

Since you have not mentioned the language of your preference, I am providing the code in JAVA.

CODE

import java.util.Scanner;

public class Main {

public static long fib(int n)

{

long a = 0, b = 1, c;

if (n == 0)

return a;

for (int i = 2; i <= n; i++) {

c = a + b;

a = b;

b = c;

}

return b;

}

public static void main(String args[])

{

Scanner sc = new Scanner(System.in);

int n;

System.out.println("Enter the value of n: ");

n = sc.nextInt();

long start = System.currentTimeMillis();

System.out.println(fib(n));

long end = System.currentTimeMillis();

System.out.println("Time taken = " + (end - start) + "ms");

}

}

a) Time taken by the code = 1 ms

b) 49th term is 7778742049

c) The running time of this program is O(n).