Complexity running times LAB and fibonacci numbers (java)

have been looking the page and lots of great people helping outhere so i have a开发者_Go百科 Lab Assignment and i know i have to do a method concerning the fibonacci numbers to caclulate the number in the position n, but im not quite sure what do put inside the method i know is what i have to think about hope you can give and idea. Having trouble.(not asking to do the hw for me ok) Thank you.

1. Fibonacci numbers and complexity

Fibonacci numbers are defined recursively as follows:

F(n) = n, for n<=1

F(n) = F(n-1) + F(n-2) for n>1

Write the following methods to compute F(n):

a) A O(2n^n) method based on the recursive definition

b) A O(n) method that uses a loop

c) A O(1) method that uses the closed form solution – feel free to look for this formula on line.

Test all three methods using n = 10; 20; 50; 100; 1,000; 10,000; 100,000 and 1,000,000. If a particular algorithm and input combination does not return an answer in a reasonable amount of time, note that in your report (that is, don’t wait for hours (or worse) for your program to finish).

Well, to answer part c there is a constant time function that will calculate the nth fibonacci number. You can find the formula for it here: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression

I assume "Hw" means homework, so no code I'm afraid.

a) O(2n) and O(n) are the same thing. Do you mean O(2^n)? This will happen if you use the recursive method without caching the results.

b) This is the "obvious" way to implement it, using a procedural implementation and remembering the last two numbers and using those to calculate the next one. In pseudo-code it would be something like loop { a, b = b, a+b; }

c) This won't work for all n unless you have infinite precision, and infinite precision isn't O(1). For example, when I use doubles fib(73) works out to be 806515533049395, but actually it is 806515533049393. The difference is due to rounding errors when working with floating point numbers.

And regarding the O(n) solution, if you are going to calculate up to fib(1000000) then a 64-bit integer isn't going to be anywhere near enough to store the result. You'll need to use BigIntegers. Adding two BigIntegers is not an O(1) operation, so the O(n) performance I mentioned before is too optimistic.