Solved

Calculate fibonacci series in linear time

Posted on 2008-10-21
4
1,096 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
[X]
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
  • 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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
NotAlone Challenge 20 88
array6 challenfge 6 121
numbers ascending pyramid 101 241
C++ statement T∗ begin(Vector<T>& x) 5 12
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…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
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…

730 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