• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1100
  • Last Modified:

Calculate fibonacci series in linear time

Is there a way to calculate the fibonacci series in linear time instead of O(n^2)?
0
ubuntuguy
Asked:
ubuntuguy
  • 2
1 Solution
 
ozoCommented:
where n means the nth  fibonacci number?
If you can do additions in O(1) then yes.
0
 
Frosty555Commented:
= get yourself a really, really big ALU chip :)
0
 
javaexpertoCommented:
This is linear I make it personally.
	public void fibonacci(int finish) {
		
		int n= finish;	
		int c= 0;	
		int e= 1;	
		int t= 0; 
		for (int i = 1; i <= n; i++) {
			t=c;
			System.out.print(c + " ");
			   
			c= c+e;        
			e= t; 	
		}		
	}

Open in new window

0
 
ozoCommented:
that's O(n) as long as f(n) is small enough to fit in an int
if adding large numbers is O(log(f(n)) then this method becomes O(n^2)
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now