Fibonacci series can be find using iteration or recursion.In iteration one for loop is used so time complexity O(n).In recursion time complexity is exponential O(2^n).
Example of fibonacci series
0,1,1,2,3,5,8
In fibonacci series
First two number is 0 or 1
next number can be found using previous two number
Next number=0+1=1
So series is
O,1,1
Next number is
=1+1=2
So series is
0,1,1,2
C program find Fibonacci series using iteration.
#include <stdio.h>
void main() {
int a[10];
int n=10;
int i;
a[0]=0;
a[1]=1;
for(i=2;i<n;i++)
{
a[i]=a[i-1]+a[i-2];
}
for(i=0;i<n;i++)
{
printf("%d,",a[i]);
}
}
C program to find Fibonacci using recursion
#include <stdio.h>
int fib(int n);
void main() {
int i;
int f;
int n=10;
for(i=0;i<n;i++)
{
f=fib(i);
printf("%d ,",f);
}
}
int fib(int n)
{
int re;
if(n<=1)
return n;
else
re=fib(n-1)+fib(n-2);
return(re);
}
Time complexity to find Fibonacci series using recursion
T(n)=T(n-1)+T(n-2)+c
Let T(n-1)==T(n-2)
So recurrence equation
T(n)=2T(n-1)+c
T(n-1)=2T(n-2)+c
Put the value of T(n-1) in T(n)
T(n)=2(2T(n-2)+c)+c
T(n)=4T(n-2)+2c+c
T(n)=4T(n-2)+3c
In general
T(n)=2^k(n-k)+(k+1)c
n-k=0
n=k
T(n)=2^nT(0)+(n+1)c
T(n)=2^n*1+(n+1)c
T(n)=2^n+(n+1)c
So time complexity is 2^n
0 Comments