ProgrammingThis 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.

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 LQ-related cookies.

Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.

Exclusive for LQ members, get up to 45% off per month. Click here for more info.

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:

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[][]?

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" ;-)):

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?

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.

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:

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]);}
}

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?

#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.

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).

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.

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