Solved

Calculate fibonacci series in linear time

Posted on 2008-10-21
4
1,094 Views
Last Modified: 2012-05-05
Is there a way to calculate the fibonacci series in linear time instead of O(n^2)?
0
Comment
Question by:ubuntuguy
  • 2
4 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 22773614
where n means the nth  fibonacci number?
If you can do additions in O(1) then yes.
0
 
LVL 31

Expert Comment

by:Frosty555
ID: 22773619
= get yourself a really, really big ALU chip :)
0
 
LVL 6

Accepted Solution

by:
javaexperto earned 500 total points
ID: 22773675
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
 
LVL 84

Expert Comment

by:ozo
ID: 22773709
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

ScreenConnect 6.0 Free Trial

Want empowering updates? You're in the right place! Discover new features in ScreenConnect 6.0, based on partner feedback, to keep you business operating smoothly and optimally (the way it should be). Explore all of the extras and enhancements for yourself!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
When we want to run, execute or repeat a statement multiple times, a loop is necessary. This article covers the two types of loops in Python: the while loop and the for loop.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question