I am given $T(n)=2T(n-1)+5^n$, and asked to find the runtime complexity. If there were no $5^n$ term, then the $T(n)$ would clearly be linear, $O(n)$. However, does the $5^n$ term make the complexity of this function $O(5^n)$?
Asked
Active
Viewed 17 times
0
-
It would not be linear without that term it would be exponential - $O(2^n)$. – Peter Foreman Apr 11 '19 at 19:18
-
@PeterForeman Why would it be exponential? Would it not just do 1 operation $n$ times until the base case was reached? – Gerardo Hemingway Apr 11 '19 at 19:20
-
Well I assumed that if $T(n)=2^n$ that would imply $O(T(n))=O(2^n)$ but you meant the number of operations performed which is completely different. – Peter Foreman Apr 11 '19 at 19:23