MUST BE sub-linear

Problem #3: (40 points) The Fibonacci sequence fibei is defined recursively as follows: The numbers in the Fibonacci sequence are called the Fibonacci numbers, for example: (a) Implement a sub-linear time complexity function in Java. fib(1)-1, fib(2)-1 and, fib(n)-fib(n-1) fib(n-2) for n 2 3. 11, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233... int fib(int n) that returns the nth Fibonacci number. Example: fib(9) returns 34. (b) What is the running time complexity of your function? Justify your answer by using the basic algorithms techniques of algorithm analysis.. Important Notes: Your Java program should print correctly the fib(250); fib(250) = 7896325826131730509282738943634332893686268675876375 In the resolution of this problem it is not allowed (and is not a good idea) to use .You must add the main method in your program in order to test your the Binet's formula. implementation There are no data errors that need to be checked as all the data will be assumed correct. Your program MUST be submitted only in source code form (.java file). A program that does not compile or does not run loses all correctness points