Develop a Fibonacci sequence evaluation function Fib_iter(n) using any programmi

Question

Develop a Fibonacci sequence evaluation function Fib_iter(n) using any programming language that can return the n^th Fibonacci value with time complexity O(n), briefly justify why it is linear. It is also known that the nth Fibonacci sequence value can be expressed as Fib(n) = a^n+b^n, where a, b are two certain constants. Write a new function Fib_formula(n) to evaluate Fib(n) with time complexity O(log n) with complexity justifications. Bonus question: derive the values of a and b mathematically, the so-called "Binet's formula".

Explanation / Answer

to find the nth term in fibonacci series

java code is

public class fibonacciSeries
{
static int fibonacci(int num)
{
   int fib[] = new int[num+1];
   int k;
  
  
   fib[0] = 0;
   fib[1] = 1;
     
   for (k = 2; k<num+1; k++)
   {
   fib[k] = fib[k-1] + fib[k-2];
   }
  
   return fib[num];
}
  
public static void main(String args[])
{
int n = 9;
System.out.println(fibonacci(n));
}
}

the time complexity of above code is o(n) since fibonacci() that actually calculates the fibonacci series has a single for loop that starts from 2 and goes till n

so time complexity is o(n)

code for fibonacci() that takes o(log n) time

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.