Learn Big O Notation and Fibonacci Sequences | CS Assignment Help

[twobagger]

My CS instructor, as an introduction to big-O notation, gave a "foreign language" assignment that requires writing a program to get the nth fibonacci number, according to the specs below. What's getting me is big-O notation, as it was ill-explained in class, and I can't seem to make heads or tails of Wikipedia's explanations. I would greatly appreciate any help offered.

Assignment Specifications:
1) Write a program in a language other than Java that uses a derivation of the Fibonacci method given below to find the nth Fibonacci number, where F(n) is the Fibonacci sequence and F(1) = F(2) = 1. (70 points)
2) Correctly incorporate at least one other method (iterative or recursive) that finds F(n) as defined in Part 1. (10 points/method, limit one recursive and one iterative method)
3) Explain the execution time of each Fibonacci method using big-O notation (O(n) or some similar). (10 points/method explained)

#include <cstdlib>
#include <iostream>

using namespace std;
unsigned fibo[25];

int fibonacci(int k) // The instructor gave this method as a reason to NOT
{                    // use recursion without considering execution times. )=
    if ((k == 1)||(k == 2))
    return 1;
    if (k < 1)
    {cout << "You tard, enter a positive integer please." << endl; return 666;}  //Handling input error 
    return fibonacci(k - 1) + fibonacci (k - 2);                                 //in 2 methods the fun way (=
}

unsigned improved(int r){
    if (r > 2)                       //making sure the user enters a positive integer
    int fibo[r];                     //greater than 2, when I can use my F(1) = F(2) = 1
    else return fibonacci(r);
    fibo[0] = 1;   // F(1) = 1
    fibo[1] = 1;   // F(2) = 1 
    for (int x = 2; x < r; x++)              // Putting in all values of the array (although unnecessary)
    {fibo[x] = fibo[x - 1] + fibo[x - 2];}  // F(n) = F(n-1) + F(n-2)
    unsigned sum = fibo[r-2] + fibo[r-3];  //Since sum = F(n) = F(r-1)
    return sum;
}

unsigned* theMatrix(unsigned fibo[], int size)
{
    fibo[0] = 1;
    fibo[1] = 1;
    for (int x = 2; x < size; x++)
    {fibo[x] = fibo[x - 1] + fibo[x - 2];}
    return fibo;
}
////////////////////////////////////
// If: the sequence of Fibonacci 
//     numbers is F(n) where F(n) =
//     F(n-1) + F(n-2), then, if n
//     is even (with F(1) = F(2) = 1),
//     F(n) = 1 + (1)F(n-2) + 1 + 2F(n-4)
//            + 1 + 3F(n-6) + 1 + ...
//            ... + (n/2)F(2) + 1.
//     If n is odd, then 1 is not added
//     until the very end, and the sum is 
//     instead 1F(n-2) + 2F(n-4) +
//             ... + (n/2)F(1) + 1.
/////////////////////////////////////
unsigned yar(int index, int multiplier, unsigned fibo[]){ //fibonacci method?
    if ((index == 1) || (index == 2)) //Exit condition
       return 1;  //no multipliers here because (number - 3) is negative.
    return ((index+1)%2) + multiplier*fibo[index-3] + yar(index - 2, multiplier + 1, fibo);
}   // The above line adds one if n is even, then adds multiplier * (n-3)th fibonacci number, then
    // calls the method again, decrementing the index and incrementing the multiplier
    

int main()
{
    int rows = 0;
    cout << "Find which Fibonacci number?" << endl;
    cin >> rows;
    theMatrix(fibo, rows);
    unsigned display1 = yar(rows, 1, fibo);
    cout << "The number is: "; 
    cout << display1 << endl;
    unsigned display2 = improved(rows);
    cout << "The number is: ";
    cout << display2 << endl;
    system("PAUSE");
    return 0;
}

Through some convoluted method, I arrived at O((N-2)^2) for the fibonacci() method, which my instructor insists is improper.
Once again, any help is appreciated. Thanks in advance.

 

[0rthodontist]

First, the point of O notation is to simplify complicated expressions like (n-2)^2. If a function is O((n-2)^2), it is also O(n^2) and it's better to write it that way (though you aren't correct anyway).

A simple idea of O notation is that if f(n) = O(g(n)), then you can shrink f(n) by some constant factor greater than 0, and if you shrink it enough the shrunken function will always be less than g(n).

Your fibonacci() function happens to be exactly as complex as the fibonacci sequence itself. You could try counting the number of times fibonacci() is called on input 1, 2, 3, 4, or 5, and see if that gives you any idea. You can prove it by induction.

 

[twobagger]

Ok. It looks like the fibonacci sequence would be roughly O(2^n).
One last thing: does every command influence n, or just certain ones?

 

[0rthodontist]

No, fibonacci() is not O(2^n). Can you fill in the following table?

n   number of calls to fibonacci()
1       1
2       1
3       ?
4       ?
5       ?

 

[twobagger]

No? Ok...

n   number of calls to fibonacci()
1       1
2       1
3       3
4       5
5       9

I thought that since (almost) each call to the fibonacci() method caused 2 more calls, then the complexity would be 2^n?

 

[Sane]

The fibonacci sequence is roughly 2^(0.694n).

To even find the 250th value, will take 2^(0.694*250) = 2^173 atomic operations. This will never be able to terminate, even on the world's fastest computer.


In your improved function, you assess the fact that storing it in an array is unecessary. So why do you still do it?

You declare fibo as a global, but only use that declaration in a pass to Matrix. Arrays are always passed by reference, so having the modified version accessable outside of Matrix doesn't require that you make it global.

You declare fibo[r] at one point, which is assigning a dynamic size to a static array. It is more formally recommended to make the memory block dynamic, and free the memory that was dynamically allocated, or else consequently encounter memory leaks.

Besides all of this, your program doesn't seem to produce the correct output.

 

[0rthodontist]

No? Ok...

n   number of calls to fibonacci()
1       1
2       1
3       3
4       5
5       9

Okay, now let a_n be the number of calls to fibonacci() when the input is n. Can you express a_n in terms of a_n-1 and a_n-2?

Maybe you don't know how to solve that yet, but you can at least say that your fibonacci is O(a_n) time once you've recursively defined a_n.

 

[twobagger]

Sane:

In your improved function, you assess the fact that storing it in an array is unecessary. So why do you still do it?

When you ask why I still do it, do you mean to ask why I use an array at all, or why I store values to the array in that method?
I use the array because my goal in writing this program was to improve on the fibonacci() method, and using an array seemed like it would cut down on the amount of time it takes to calculate each fibonacci number. And I store values to the array in that method because I had not yet written the other methods that store the values for me. Thanks for pointing that out to me.

You declare fibo as a global, but only use that declaration in a pass to Matrix. Arrays are always passed by reference, so having the modified version accessable outside of Matrix doesn't require that you make it global.

I was unsure about how to use the array, as every time I tried without the global statement, I received error messages. They stopped when I made fibo global, so I stopped trying to correct them.

You declare fibo[r] at one point, which is assigning a dynamic size to a static array. It is more formally recommended to make the memory block dynamic, and free the memory that was dynamically allocated, or else consequently encounter memory leaks.

I do not understand how to do this. Maybe I should have declared fibo to be of size 47?

Besides all of this, your program doesn't seem to produce the correct output.

I disagree. With every input integer less than or equal to 47, my program appeared to give the correct Fibonacci number twice, once for each method I call. Greater than that, it seemed that I'd hit some size limitation.

0rthodontist:
a_n = a_(n-1) + a_(n-2) + 1 for n >= 2, it looks like.
= 2a_(n-2) + a_(n-3) + 2
= 3a_(n-3) + 2a_(n-4) + 4
= F(k+1)*a_(n-k) + F(k-1)*a_(n-(k+1)) + 2k - 1
= F(n-1) + F(n-3) + 2n - 5 for k = (n-2)
Is any of this what you're trying to lead me towards?

Thank you both for your patience with me.

 

[Sane]

When you ask why I still do it, do you mean to ask why I use an array at all, or why I store values to the array in that method?

Why do you use it at all? You could shuffle between a couple temporary values to synthesize a queue, or actually use a queue, which would reduce the need for an array to store all the intermediate values. That method is much more memory efficient when computing higher values of the fibonacci sequenece. For values below 50, you would not see any difference, so it's nothing to worry about.

I was unsure about how to use the array, as every time I tried without the global statement, I received error messages. They stopped when I made fibo global, so I stopped trying to correct them.

That doesn't sound right. I'll edit this post in a moment with it working without fibo being global.

I do not understand how to do this. Maybe I should have declared fibo to be of size 47?

I'm sorry. I should have checked my sources before I said that. It seems that in C++, defining an array with constant size has the same effect as defining with an invariable bound. I've been spending too much time in C.

Edit:

Okay, I turned fibo into a local. But while doing so, I stumbled across some more strange things.

In the function "theMatrix", you should not be returning anything. In your calling routine, you do not even assign anything to the return value from the function, nor would you need to anyways.

In the function "improved", you return "fibo[r-2] + fibo[r-3]", when you could just return "fibo[r-1]". After all, by definition, t_(r-1) = t_(r-2) + t_(r-3).

Given these changes, "theMatrix" and "improved" are essentially the exact some function. What's the distinction?

And then finally, you could take advantage of the transitive properities of programming, and not worry about assigning everything to a variable, such as "display1" and "display2". You could insert the return value directly into the cout statement.

And can I just assume "yar" is a silly hypothetical function, which bears no intentional importance?

You should also look into the proper way of handling errors, as opposed to returning 666.

#include <cstdlib>
#include <iostream>
using namespace std;

int fibonacci(int k) // The instructor gave this method as a reason to NOT
{                    // use recursion without considering execution times. )=
    if ((k == 1)||(k == 2))
    return 1;
    if (k < 1)
    {cout << "You tard, enter a positive integer please." << endl; return 666;}  //Handling input error 
    return fibonacci(k - 1) + fibonacci (k - 2);                                 //in 2 methods the fun way (=
}

unsigned improved(unsigned fibo[], int r){
    if (r <= 2) return fibonacci(r);          // making sure the user enters a positive integer
        
    fibo[0] = 1;   // F(1) = 1
    fibo[1] = 1;   // F(2) = 1 
    
    for (int x = 2; x < r; x++)              // Putting in all values of the array (although unnecessary)
    {
        fibo[x] = fibo[x - 1] + fibo[x - 2]; // F(n) = F(n-1) + F(n-2)
    }  
    return fibo[r-1];
}

void theMatrix(unsigned fibo[], int size)
{
    fibo[0] = 1;
    fibo[1] = 1;
    for (int x = 2; x < size; x++)
    {
        fibo[x] = fibo[x - 1] + fibo[x - 2];
    }
}

unsigned yar(int index, int multiplier, unsigned fibo[]) { //fibonacci method?
    if (index == 1 || index == 2) //Exit condition
        return 1;  //no multipliers here because (number - 3) is negative.
    return ((index+1)%2) + multiplier*fibo[index-3] + yar(index - 2, multiplier + 1, fibo);
}   

// The above line adds one if n is even, then adds multiplier * (n-3)th fibonacci number, then
// calls the method again, decrementing the index and incrementing the multiplier
    

int main()
{
    int rows;
    unsigned fibo[25];
    
    cout << "Find which Fibonacci number?" << endl;
    cin >> rows;
    
    theMatrix(fibo, rows);
    cout << "The number is: "; 
    cout << yar(rows, 1, fibo) << endl;
    
    cout << "The number is: ";
    cout << improved(fibo, rows) << endl;
    
    system("PAUSE");
    return 0;
}

 

[twobagger]

Why do you use it at all? You could shuffle between a couple temporary values to synthesize a queue, or actually use a queue, which would reduce the need for an array to store all the intermediate values. That method is much more memory efficient when computing higher values of the fibonacci sequenece. For values below 50, you would not see any difference, so it's nothing to worry about.

That never occurred to me. Thank you for suggesting it.

In the function "theMatrix", you should not be returning anything. In your calling routine, you do not even assign anything to the return value from the function, nor would you need to anyways. . . . "theMatrix" and "improved" are essentially the exact some function. What's the distinction?

I had intended to use "theMatrix" as a method to initialize the array, however, I received an error method when I tried to return the array and assign that value to the fibo[] array. So I used the code in that method as my base for the "improved" method.

And can I just assume "yar" is a silly hypothetical function, which bears no intentional importance?

Silly and hypothetical, you say? It works, and its presence honors all pirates. Yarrrrrr.
So yes.

You should also look into the proper way of handling errors, as opposed to returning 666.

Oh, bah, humbug, fine. This any better?

int fibonacci(int k) 
{                   
    try{
    if ((k < 1) || (k > 47)) throw k; //tossing anything not between 1 and 47, including most characters
    if ((k == 1)||(k == 2))           //it still only truncates decimals
    return 1;
    else return fibonacci(k-1) + fibonacci(k-2);
    }
    catch (int k){cout << "No. Not going to work. Uh-uh." << endl; return 0;}
}

By the way, does c++ not have a "finally" statement?

 

[Jheriko]

By the way, does c++ not have a "finally" statement?

It doesn't, but if you are using Microsoft C++ there is the ms-specific keyword __finally.

If you just want to use "finally" to make sure that something gets deallocated and are not using msvc++ then a 'workaround' is to wrap whatever it is in a 'thin' and 'lightweight' class and write a constructor/destructor to do the memory management. This way when an exception is thrown the destructor gets called appropriately as the stack unwinds and there is no memory leak.

EDIT: there is also catch(...) which catches all exceptions... which might be more suitable.

Hope this helps.

 

[Sane]

Oh, bah, humbug, fine. This any better?

Your professor will be thrilled. :tongue2:

 

[NateTG]

The fibonacci sequence is roughly 2^(0.694n).

To even find the 250th value, will take 2^(0.694*250) = 2^173 atomic operations. This will never be able to terminate, even on the world's fastest computer.

Actually, the N'th fibonacci number can be found in $O(n)$ time, and it's impossible to do better unless you write it in non-decimal notation since it will have some constant times n digits. Naively generating forwards, or using a lookup table is $O(n^2)$.

 

[NateTG]

I disagree. With every input integer less than or equal to 47, my program appeared to give the correct Fibonacci number twice, once for each method I call. Greater than that, it seemed that I'd hit some size limitation.

You're running into problems because of integer overflow. In C/C++ normal integers are limited by the machine - you're running on a 32 bit machine, right?

 

[Sane]

Actually, the N'th fibonacci number can be found in $O(n)$ time, and it's impossible to do better unless you write it in non-decimal notation since it will have some constant times n digits. Naively generating forwards, or using a lookup table is $O(n^2)$.

Of course ... I was observing his recursive algorithm, not the iterative one.

 

[twobagger]

You're running into problems because of integer overflow. In C/C++ normal integers are limited by the machine - you're running on a 32 bit machine, right?

I don't know what you mean, $4 machine. All I know is that Java has a nice BigInteger class to deal with this sort of thing, while C++ by comparison may as well be tripping old people in the middle of traffic with all the help it's giving me.