I need to obtain the upper bound time complexity (Big-O) for the below recurrence relation:
$T(n) = T(\frac{n}{3}) + T(\frac{2n}{3} + 4) + a\times n$
It is clearly not linear, so I tried the substitution method for $n\log n$ but the substitution became quite complex without a easy solution (finding a valid constant $c$)? Is there an easier way to solve the above relation to get $O$ bounds?
Use Akra-Bazzi method :(read Wikipedia page to understand the conditions and the method)
First find $p$ which is $\left(\frac{1}{3}\right)^p + \left(\frac{2}{3}\right)^p =1$ this gives us that $p=1$
Now why we did not care about the $4$ in the term $\frac{2n}{3}+4$ because one of the conditions to apply the method is that $b_i x + h_i(x)$ such that $h_i(x)$ is less than a constant multiplied by $\frac{x}{\ln^2 x}$ and we know in this case that $4$ is negligible.
$g(x) = a x$ in your case.
So $T(x) = O(x^p(1+\int \limits_{1}^{x} \frac{g(u)}{u^{p+1}} du)$)
Which is just $T(x) = O(x(1+\int \limits_{1}^{x} \frac{a u}{u^2} du)$)
Which is just $T(x) = O(x(1+a \ln x)) = O(a x \ln x) = O(x \ln x)$ for fixed $a$.