What is the time complexity of the above concept?

#1

What is the time complexity for smaller no. as well as larger no.?

#2

@priya_Jain,
You mean complexity of fibonacci recurrence?
Its simply O(n), because to compute fib(n) you calculate each fib(1) to fib(n), each being done in O(1).

#3

You said O(n) but in the Program on hackerblocks :-“Take as input N, a number. Write a recursive function to calculate Nth Fibonacci. Target complexity is O(N)” . It is showing TLE on passing my program. Here is my program:-https://ide.codingblocks.com/s/319423

#4

@priya_Jain
Hey
complexity of your code is O(2*n) because at each level u are making 2 calls .
Recursive fibonacci is 2^n
but Iterative version or recursive version with memoization is O(n)
So try to implement memoization in your code.
If you haven’t done Dynamic Programming Module then come back to this problem in future.
I hope this resolves your query :slight_smile: