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.(adsbygoogle = window.adsbygoogle || []).push({});

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.Code (Text):#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;

}

Once again, any help is appreciated. Thanks in advance.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Big O Notation Question

Loading...

Similar Threads for Notation Question |
---|

C/++/# Question about running "executables" without source code |

Big-O Notation Question |

C/++/# Question about input format file (for creating a net) |

Latex article template question |

C/++/# Question about a specific class method in C++ |

**Physics Forums | Science Articles, Homework Help, Discussion**