time complexity for all fibonacci numbers from 0 to n
Clash Royale CLAN TAG#URR8PPPtime complexity for all fibonacci numbers from 0 to n
I was calculating the time complexity of this code that prints all Fibonacci numbers from 0 to n. According to what I calculated, the fib() method takes O(2^n) and since it is being called i number of times, so it came out to be O(n*2^n). However, the book says it is O(2^n). Can anyone explain why the time complexity here will be O(2^n) ?
fib()
O(2^n)
i
O(n*2^n)
O(2^n)
O(2^n)
Here is the code:
void allFib(int n){
for(int i = 0 ; i < n ; i++){
System.out.println(i + ": " + fib(i));
}
}
int fib(int n ){
if(n <= 0) return 0;
else if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}
@Am_I_Helpful please read the question carefully before marking it duplicate. The content in the link you provided is not the answer to my question.
– Yuva K
7 mins ago
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
Possible duplicate of Computational complexity of Fibonacci Sequence
– Am_I_Helpful
15 mins ago