Click here to download the IntelliJ project for this exercise. Alternatively, you can find all the exercices on this git repository
This exercise is already available in your IntelliJ as a project.
What you need to do is described in the comments at the top of the file in src/main/java/
.
package algorithms; /** * This class provides a (recursive) method to compute Fibonacci numbers using recursion. * * Our feeling is that the time complexity of this method is not optimal. * 1) Do an analysis of the time complexity of this method in function of n * 2) Implement a more efficient method to compute Fibonacci numbers. * Your method should have a time complexity of O(n) and space complexity of O(1). * * Your final method doesn't need to be recursive. */ public class Fibonacci { /** * Computes the nth Fibonacci number. * * @param n The position of the Fibonacci number to compute. It should be non-negative. * @return The nth Fibonacci number. * @throws IllegalArgumentException if n is negative. */ public static long fibonacci(long n) { if (n < 0) { throw new IllegalArgumentException("n should be non-negative"); } if (n <= 1) { return n; } return Math.addExact(fibonacci(n - 1) , fibonacci(n - 2)); // I use addExact to avoid silent overflow } }
- Instruction provided at the top of the source file on IntelliJ.
- Debug using small and easy unit tests provided in junit tests, it can also help to clarify the instructions.