Problem #3: (40 points)

The Fibonacci sequence {fib}i1 is defined recursively as follows:

fib(1) = 1, fib(2) = 1 and, fib(n) = fib(n-1) + fib(n-2) for n 3.

The numbers in the Fibonacci sequence are called the Fibonacci numbers, for example:

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233}

(a) Implement a sub-linear time complexity function in Java.

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..

Problem #3: (40points! The Fibonacci sequence ffib21 is defined recursively as follows: fib(1)1, fib(2)-1 and, fib(n) - fib(n-1) + fib(n-2) for n The numbers in the Fibonacci sequence are called the Fibonacci numbers, for example: 2 3 11, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233... (a) Implement a sub-linear time complexity function in Java 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