LinuxQuestions.org
Visit the LQ Articles and Editorials section
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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

Reply
 
Search this Thread
Old 09-09-2006, 04:26 PM   #1
debiant
Member
 
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196

Rep: Reputation: 30
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_SIZE-3;i++){
		x[i]=x[i-1]+x[i-2];
		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[][]?
 
Old 09-09-2006, 04:45 PM   #2
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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
 
Old 09-09-2006, 05:23 PM   #3
debiant
Member
 
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196

Original Poster
Rep: Reputation: 30
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?
 
Old 09-09-2006, 08:12 PM   #4
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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.
 
Old 09-09-2006, 08:28 PM   #5
debiant
Member
 
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196

Original Poster
Rep: Reputation: 30
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.
 
Old 09-09-2006, 09:25 PM   #6
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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.
 
Old 09-09-2006, 09:27 PM   #7
debiant
Member
 
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196

Original Poster
Rep: Reputation: 30
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[row-1][col]+x[row-1][col+1];
			else
				x[row][col]=x[row-1][col]+x[row][col-1];
			printf(", %.0f", x[row][col]);}
				
		
}
 
Old 09-09-2006, 09:38 PM   #8
debiant
Member
 
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196

Original Poster
Rep: Reputation: 30
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[row-1][0]+x[row-1][1];
		x[row][1]=x[row-1][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; 09-09-2006 at 09:40 PM.
 
Old 09-09-2006, 09:43 PM   #9
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 111Reputation: 111
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[row-1][0]+x[row-1][1];
      x[row][1]=x[row-1][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.
 
Old 09-09-2006, 09:45 PM   #10
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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.
 
Old 09-09-2006, 10:00 PM   #11
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 111Reputation: 111
It isn't the only way to get O(1), as long as you don't include compile time into the equation...
 
Old 09-09-2006, 10:14 PM   #12
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
tuxdev -

Do you mean using preprocessor macros?
 
Old 09-09-2006, 10:22 PM   #13
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 111Reputation: 111
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.
 
Old 09-09-2006, 11:10 PM   #14
debiant
Member
 
Registered: Jul 2006
Distribution: Source Mage 0.9.6
Posts: 196

Original Poster
Rep: Reputation: 30
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
Big O, Big Omega, and Big Theta oulevon Programming 7 05-26-2010 07:18 AM
boot sequence system text - too big fonts.. captain skywave Suse/Novell 2 06-24-2005 05:19 AM
pointer notation vs array notation? pablowablo Programming 5 03-14-2005 12:34 PM
need perl help calculating fibonacci numbers WorldBuilder Programming 5 12-17-2003 01:41 AM
Finding a real value for constant in Big O notation oulevon Programming 6 10-17-2003 05:04 PM


All times are GMT -5. The time now is 01:57 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration