Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Calculate fibonacci series in linear time

Posted on 2008-10-21
4
1,095 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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
constructor while deserilizing object 16 57
wordappend challenge 8 200
C# code editing and collaboration 3 134
AvlTree-Node Data type 4 14
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

838 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