Solved

Calculate fibonacci series in linear time

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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say 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

Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
This article will show, step by step, how to integrate R code into a R Sweave document
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

728 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