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.

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.

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.