time complexity for all fibonacci numbers from 0 to n
Clash Royale CLAN TAG #URR8PPP time 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); } Possible duplicate of Computational complexity of Fibonacci Sequence – Am_I_Helpful 15 mins ago @Am...