- #1
twobagger
- 7
- 0
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)
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.
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)
Code:
#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.