Получите верхнюю и нижнюю оценки для T (n) = 3T (n / 5) + T (n / 2) + 2 ^ n

Question

У меня есть повторение, где T(n) = 3T(n/5) + T(n/2) + 2^n, и я хочу найти верхнюю и нижнюю границы для T (n).

Но я не могу использовать метод 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).