Solved

# Calculate fibonacci series in linear time

Posted on 2008-10-21
1,098 Views
Is there a way to calculate the fibonacci series in linear time instead of O(n^2)?
0
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
• 2

LVL 84

Expert Comment

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

LVL 31

Expert Comment

ID: 22773619
= get yourself a really, really big ALU chip :)
0

LVL 6

Accepted Solution

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;
}
}
``````
0

LVL 84

Expert Comment

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

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 …
###### Suggested Courses
Course of the Month7 days, 21 hours left to enroll