Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game. 
Notices 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 


09092006, 05:26 PM

#1

Member
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196
Rep:

Big O notation  fibonacci sequence
I found a book online about algorithms, and as The C Programming Language was starting to get into some algorithms that I didn't quite understand (or weren't familiar with) I thought I would try to brush up, then I start learning about big O notation and now I'm completely off the track of where I was, but I'm still learning so it can't be all bad. The book http://www.cse.ucsd.edu/~dasgupta/mcgrawhill/ starts in the Prologue with a discussion of the fibonacci sequence, so I created a program to display the fibonacci sequence:
Code:
#include <stdio.h>
#define FIB_ARRAY_SIZE 150
int main(void)
{
double x[FIB_ARRAY_SIZE]={0,1,1};
int i;
printf("0, 1, 1");
for(i=3;i<FIB_ARRAY_SIZE3;i++){
x[i]=x[i1]+x[i2];
printf(", %.0f, ",x[i]);}
}
Could anyone walk me through how you determine the big O notation of this code. Also, the book alludes to a matrix solution that has a log(n) efficiency. Would this be the same as an array[][]?



09092006, 05:45 PM

#2

Guru
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Rep:

Hi 
1. My favorite book reference is Sedgewick: "Algorithms in Java":
http://www.cs.princeton.edu/~rs/
2. Here's a good discussion of BigO notation (among other things, you'
learn how to compare the complexity of the song "American Pie" vs "99 Bottles of Beer" ;)):
http://www.cs.sunysb.edu/~algorith/l...ood/node2.html
3. I have no idea if the code you posted is actually *correct* or not...
... but as far as it's "complexity": it'a s simple loop.
I would say its performance is "linear" (the time to execute the program
increases linearly as FIB_ARRAY_SIZE increases).
So I would say its "BigO" value i O(n)
4. As far as an "O(log n)" fibonacci implementation: sure! Maybe! Sounds plausible ;)
But I honestly don't know.
'Hope that helps .. PSM



09092006, 06:23 PM

#3

Member
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196
Original Poster
Rep:

Well the code is correct in as much as it produces the correct values, so with an efficiency of O(n) that is not too bad, but it would be better with a O(log n).
How will putting the values into a matrix improve the efficiency?



09092006, 09:12 PM

#4

Guru
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Rep:

I wouldn't want to deprive you of your Nobel Prize in math by not letting you figure it out yourself now, would I?
http://mathforum.org/social/articles/ross.html
Last edited by paulsm4; 09092006 at 09:13 PM.



09092006, 09:28 PM

#5

Member
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196
Original Poster
Rep:

I wish I were a student again. I squandered so many opportunities for learning in college. Now I'm in a job I love, but not exactly the field I wanted. If I knew then what I know now, and could learn what I should have learned then, then I would have learned what I now want to know.
I'll keep looking. I know this looks like a homework assignment, but it's really not, I'm just a wannabe nerd without the mathematical chops to get through all this algorithm stuff.



09092006, 10:25 PM

#6

Guru
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Rep:

Hi 
Fair enough (and I confess  again!  that I didn't know, either ;)).
Comparative implementations of the Fibonacci sequence (with O(n^2), O(n) and O(log n)) efficiencies), along with an answer to your question, can be found here:
http://en.wikipedia.org/wiki/Fibonacci_number_program
PS:
My Google search was "C++ fibonacci Binet’s formula"
PPS:
If you're not already familiar with them, this might be a good excuse to download and play with the Ruby and/or Python languages.
Last edited by paulsm4; 09092006 at 10:27 PM.



09092006, 10:27 PM

#7

Member
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196
Original Poster
Rep:

Ok, I came up with a matrix version of the fibonacci program, although as cryptic as it seems, I don't understand how it can be faster. If this is the O(log n) that I was looking for, could somebody help me understand why?
Code:
#include <stdio.h>
#define FIB_ARRAY_SIZE 150
#define COL 2
int main(void)
{
int row, col;
double x[FIB_ARRAY_SIZE][COL]={0,1};
printf("%.0f, %.0f", x[0][0],x[0][1]);
for(row=1;row<FIB_ARRAY_SIZE;row++)
for(col=0;col<2;col++){
if(col==0)
x[row][col]=x[row1][col]+x[row1][col+1];
else
x[row][col]=x[row1][col]+x[row][col1];
printf(", %.0f", x[row][col]);}
}



09092006, 10:38 PM

#8

Member
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196
Original Poster
Rep:

ok, I'm filling up my own thread, but I was just thinking that that function makes one loop twice * ARRAY_SIZE. Where as this:
Code:
#include <stdio.h>
#define FIB_ARRAY_SIZE 150
#define COL 2
int main(void)
{
int row, col;
col=0;
double x[FIB_ARRAY_SIZE][COL]={0,1};
printf("%.0f, %.0f", x[0][0],x[0][1]);
for(row=1;row<FIB_ARRAY_SIZE;row++){
x[row][0]=x[row1][0]+x[row1][1];
x[row][1]=x[row1][1]+x[row][0];
printf(", %.0f, %.0f", x[row][0],x[row][1]);}
}
only makes the loop * FIB_ARRAY_SIZE and produces twice as many numbers from the fibonacci sequence. Now I know constant multiplication isn't supposed to mean much in big O notation, but are either of these solutions the O(log n) I'm looking for?
Last edited by debiant; 09092006 at 10:40 PM.



09092006, 10:43 PM

#9

Senior Member
Registered: Jul 2005
Distribution: Slackware
Posts: 2,014
Rep:

Simplified, that code is equavalent to:
Code:
#include <stdio.h>
#define FIB_ARRAY_SIZE 150
#define COL 2
int main(void)
{
int row, col;
double x[FIB_ARRAY_SIZE][COL]={0,1};
printf("%.0f, %.0f", x[0][0],x[0][1]);
for(row=1;row<FIB_ARRAY_SIZE;row++)
{
x[row][0]=x[row1][0]+x[row1][1];
x[row][1]=x[row1][1]+x[row][0];
printf(", %.0f", x[row][col]);
}
}
That doesn't look like O(log n) to me. It still looks like O(n), since it calulates exactly two more fibonaci numbers each iteration. It still takes the same amount of calcualation. You will not do any better than O(n) while you are still using induction. There is actually a way to do these in O(1) time.



09092006, 10:45 PM

#10

Guru
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Rep:

Hi, again 
You can easily find out yourself by actually *running* the two programs and comparing their execution times.
If you're not already familiar with it, this might also be a good excuse to play with "gprof" (if you're using GCC):
http://linuxgazette.net/100/vinayak.html
Alternatively, you could create a pair of functions to take your own timings, using:
Windows:
GetTickCount ()
Linux:
gettimeofday()
PS:
No, it doesn't look O(log n) to me, either.
Look at the Wikipedia article I cited above, that will show you what you're *really* looking for ... but it's in Python, not C++.
PPS:
The only way to do it in O(1) time is with a table.
Which, if you're willing to deal with a finite range, and you're willing to trade space for time, is a perfectly acceptable solution!
Last edited by paulsm4; 09092006 at 10:49 PM.



09092006, 11:00 PM

#11

Senior Member
Registered: Jul 2005
Distribution: Slackware
Posts: 2,014
Rep:

It isn't the only way to get O(1), as long as you don't include compile time into the equation...



09092006, 11:14 PM

#12

Guru
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Rep:

tuxdev 
Do you mean using preprocessor macros?



09092006, 11:22 PM

#13

Senior Member
Registered: Jul 2005
Distribution: Slackware
Posts: 2,014
Rep:

I was actually thinking about templates. I'm not sure how a preprocessor macro can have a proper base case, but then again, I don't know all of the preprocessor commands. The O(1) also assumes that the compiler optimizes out math with just constants (when using the preprocessor). Otherwise, it is just a really fast O(n).
Last edited by tuxdev; 09092006 at 11:26 PM.



09102006, 12:10 AM

#14

Member
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196
Original Poster
Rep:

paul thanks for the link, I now realize that O(log n) functions (at least at this point) are well out of my comprehension). I will however keeping studying on big O, and see if I can't grasp that concept at least.
Thanks for your help fellas.



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 12:19 AM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

