algorithm - 导出 T(n) = 3T(n/5) + T(n/2) + 2^n 的上限和下限

Question

我有一个循环，其中 T(n) = 3T(n/5) + T(n/2) + 2^n 我想找到 T( n).

但是，我无法使用 master 方法来解决复发问题。我刚刚学习了递归，似乎解决这个问题太难了。你能帮我解决这个问题吗？无法使用master方法怎么解决？

Answer 1

you cant solve this relation with akra-bazzi method because 2^n is not polynomial .
But for solving with finding bounds :

it's obvious that:

1)  T(n) >= 2^n (cause we can see in the relation we have 2^n and other things :)) ) 
and we know that the :

2) T(n) <= 4T(n/2) + 2^n . and we can solve this with master method and the answer of 4t(n/2) + 2^n is θ(2^n) .

1+2) now we have this : θ(2^n) <= T(n) <= 2^n . 

so we have the answer :
T(n) ∈  θ(2^n).