(Rewrote to give a better answer.)
Here is a simple and rigorous analysis that shows why T(n) ~ 4^{n/3} is a tight estimate.
We have the recurrence
T(n) = 4T(n-3) + 4T(n/2)
To get the tight result, we want to see that T(n/2) is negligible compared to T(n-3). We can do this as follows.
First, T is nonnegative for all n, so in particular T(n/2) >= 0, so for all n we have an inequality,
T(n) >= 4T(n-3)
Now, we want to use that inequality to compare T(n-3) and T(n/2).
By applying that inqeuality n/6 - 1 times, we get that
T(n-3) >= 4^{n/6 - 1} * T(n/2)
(Because, (n/6 - 1) * 3 = n/2 - 3, and n/2 - 3 + n/2 = n - 3).
It implies that T(n/2) is small compared to T(n-3):
T(n/2) <= 4^{-n/6 + 1} * T(n-3)
Now, for any epsilon > 0, there is an n_0 such that for n > n_0, 4^{-n/6 + 1} < epsilon. (Because, the limit of 4^{-n/6 + 1} is zero as n gets large.)
This implies that for any epsilon > 0, there is large enough n so that
4T(n-3) <= T(n) <= (4 + epsilon) T(n-3)
This yields the tight bound T(n) = 4^(n/3 + o(n)).
Getting a sharper estimate
There's some question in the comments about getting rid of the o(n) above, to get an even sharper estimate.
I fear this is basically just going to get pedantic -- usually no one cares about the low order terms, and nailing them down exactly is just some calculus work. But we can do a little more today anyways.
What's the difference
First of all, what is the difference between O(4^{n/3}) and 4^{n/3 + o(n)}? (Alternatively, we could write the latter as (4+o(1))^{n/3}.)
The difference is in how tightly they control the low order terms. O(4^{n/3}) controls them very tightly -- it says you don't exceed the (concrete) value 4^{n/3}) by more than a constant factor.
4^{n/3 + o(n)}, allows that you may exceed 4^{n/3} by more than a constant factor. But that factor is subexponential in n, it's negligible compared to 4^{n/3}.
For example, consider the function f(n) = n * 4^{n/3}. This function is not O(4^{n/3}). Indeed, it exceeds it by a factor n, more than a constant factor.
However, f(n) is in the class 4^{n/3 + o(n)}. Why? Because n = O(4^{epsilon n}) for every epsilon > 0.
When you have an inequality like,
4T(n-3) <= T(n) <= (4 + epsilon) T(n-3)
for every epsilon > 0, you can only deduce from this T(n) = (4 + o(1))^{n/3}.
To get a sharper bound, we need to treat epsilon as a function of n and not as a constant (like I did in the lazier version.)
Proof
Let epsilon(n) = 4^{-n/6 + 1} in what follows. Then we already showed
T(n) <= (4 + epsilon(n)) T(n-3)
and we want to see T = O(4^{n/3}).
This is can be expanded as an iterated product:
T(n) = PI_{i=1}^{n/3} (4 + epsilon(3i))
We can factor each term and pull out a factor of 4 to get
T(n) = 4^{n/3} * PI_{i=1}^{n/3} (1 + epsilon(3i)/4 )
The goal is now to show that
PI_{i=1}^{n/3} (1 + epsilon(3i)/4 ) = O(1)
and then we will be finished.
To do this we take the log, and show that that is O(1).
SUM_{i=1}^{n/3} log(1 + epsilon(3i/4))
We bound that using log(1+x) <= x for x >= 0.
SUM_{i=1}^{n/3} epsilon(3i/4)
Now we use the definition of epsilon. In fact we only need to know epsilon(n) <= C^{-n} for some C > 1. The above becomes
SUM_{i=1}^{n/3} C'^{-i}
for some constant C' > 1. But this is a geometric series, so it is bounded above by the infinite geometric series as
1 / (1 - 1/C') = O(1)
Thus T(n) = O(4^{n/3}).
Since we already had T(n) = Omega(4^{n/3}) we now have it tight up to constants, T(n) = Θ(4^{n/3})
You can decide for yourself if this extra work made things any more clear :p Personally I prefer to leave the o(n)'s in there usually.
