Welcome to the most active Linux Forum on the web.
 LinuxQuestions.org Big O notation - fibonacci sequence
 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.

 09-09-2006, 04:26 PM #1 debiant 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 #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
 09-09-2006, 04:45 PM #2 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 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 Big-O 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 "Big-O" 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
 09-09-2006, 05:23 PM #3 debiant 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?
 09-09-2006, 08:12 PM #4 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 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; 09-09-2006 at 08:13 PM.
 09-09-2006, 08:28 PM #5 debiant 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.
 09-09-2006, 09:25 PM #6 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 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; 09-09-2006 at 09:27 PM.
 09-09-2006, 09:27 PM #7 debiant 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 #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
 09-09-2006, 09:38 PM #8 debiant 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 #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
 09-09-2006, 09:43 PM #9 tuxdev Senior Member   Registered: Jul 2005 Distribution: Slackware Posts: 2,012 Rep: Simplified, that code is equavalent to: Code: ```#include #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
 09-09-2006, 09:45 PM #10 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 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; 09-09-2006 at 09:49 PM.
 09-09-2006, 10:00 PM #11 tuxdev Senior Member   Registered: Jul 2005 Distribution: Slackware Posts: 2,012 Rep: It isn't the only way to get O(1), as long as you don't include compile time into the equation...
 09-09-2006, 10:14 PM #12 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 Rep: tuxdev - Do you mean using preprocessor macros?
 09-09-2006, 10:22 PM #13 tuxdev Senior Member   Registered: Jul 2005 Distribution: Slackware Posts: 2,012 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; 09-09-2006 at 10:26 PM.
 09-09-2006, 11:10 PM #14 debiant 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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post oulevon Programming 7 05-26-2010 07:18 AM captain skywave SUSE / openSUSE 2 06-24-2005 05:19 AM pablowablo Programming 5 03-14-2005 12:34 PM WorldBuilder Programming 5 12-17-2003 01:41 AM oulevon Programming 6 10-17-2003 05:04 PM

LinuxQuestions.org

All times are GMT -5. The time now is 03:06 AM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -