I am sort of told that O(c^n) complexity could be the case of string permutations. but what is this specific 5^n? can anyone think of a simple algorithm with O(5^n)?thx
can anyone plz help
When time complexity is that way, it is usually related to recursive function (easier to explain). I do not have 5^n example but I have 2^n which is similar (constant^n).
Check the fibonaci function time complexity. It has
n = 1
T(n-1) = O(2n-1), therefore
T(n) = T(n-1) + T(n-2) + O(1) or it is
T(n) = O(2^(n-1)) + O(2^(n-2)) + O(1) = O(2^n)
suppose we have a number sieris like:T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4)+T(n-5) for n>=5,and we can define some number each forT(0) T(1) T(2) T(3) T(4) T(5) as base cases.
so is this a O(n^5) complexity? since the Fabonacci series is F(n)=F(n-1)+F(n-2) and it has O(2^n) complexity. is this a good reasoning?
You could say that, I suppose.