CareerCup

best case o(1) - by Eigen values AX = lamda X

avg - O(n) - go linearly from 1 to n

worst - fib(n-1) + fib(n-2)

best   -   lg(n)  ( matrix expo )

worst -   (n)

Best log(N)
Worts O(Fib(N))

Best O(1) (if you can do infinite precision calculation of doubles by solving the recursive formula and finding the solution as a function of (n) and the eigen functions of the recursion)

Worst O(2^(O(1) n)) (exponential).

If you do a naive recursive approach, such as this:

int fib(n) {
	if (n == 0)
		return 1;
	if (n == 1) 
		return 1;
	return fib(n - 1) + fib(n - 2);
}

By increasing the recursion depth by 1, the value of "n" is reduced by a constant (1 or 2). Also each recursion leads to "2" other recursions, so in general, you are doing O(2^n).

There are formula to calculate using formula so answer is O(1)

Best Case: O(1) - hash every possible answer ahead of time
Average Case: I don't know
Worst Case: O(infinite) - have a while loop that doesn't do anything useful and never breaks

That depends on how the algorithm of fibonacci has been implemented, but assuming its implemented iteratively

best case - O(1) (asking for fib(0) or fib(1))
average case and worst case O(n)

If it has been recursively implemented without memoization

best case - O(1) (asking for fib(0) or fib(1))
average and worst case is O(2^n)

If it has been implemented recursively with memoization, it will be

best case - O(1)
average & worst case - O(n)

Depends on the algorithm used. Fibonacci can be done in const time using a look up table.
Or in linear (O(n)) time using dynamic programming. Or in Exponential time (O(2^N)) using recursive calls.

Worst question.