I analyzed the code given, and found the that the code runs in this order:
T(n) =\begin{cases} 4T(\frac{n}{4})+clgn , & \text{otherwise} \\[2ex] d, & \text{if n ≤ 1} \end{cases}
I want to solve it using substantiation method, I started like this:
T(n/4) = 4T(n/4^2)+clgn/4
T(n) = 4T[4T(n/4^2)+clgn/4]+clgn #Here I substitute in the T(n/4) in T(n)
T(n) = 4^2T(n/4^2)+clgn +clgn
....
T(n) = 4^kT(n/4^k)+kclgn #General function
Then kclgn => is O(lgn) ,but what is 4^kT(n/4^k) , how I can find it out?
I'm doing it right?
For simplicity assume that $n$ is a power of 4, ie $n=4^k$. Then:
$T(n)=4T(\frac{n}{4})+c\log(n)=4(4T(\frac{n}{16})+c\log(\frac{n}{4}))+c\log(n)=16T(\frac{n}{16})+4c\log(\frac{n}{4})+c\log(n)=4^kT(1)+c(4^{k-1}\log(\frac{n}{4^{k-1}})+...+4\log(\frac{n}{4})+\log(n))$
Now use $\log_{10}(x)=\frac{\log_{4}(x)}{\log_{4}(10)}$, and $n=4^{k}$.
$T(n)=4^kT(1)+\frac{c}{\log_{4}(10)}(4^{k-1}\log_{4}(\frac{4^k}{4^{k-1}})+...+4\log_{4}(4^{k}/4)+\log_4(4^k))$ $=4^kT(1)+\frac{c}{\log_{4}(10)}(4^{k-1}+(2)4^{k-2}+...+(k-1)4+(k)4^{0})$ $=4^{k}T(1)+\frac{c}{\log_{4}(10)}(\sum_{i=1}^{k}i4^{k-i})$ $=4^{k}T(1)+\frac{c}{9\log_{4}(10)}(-3k+4^{k+1}-4)$
Finally $k=log_{4}(n)$, which means that $T(n)=\Theta(4^{k+1})=\Theta(n)$
(I believe I spot an error in your workings, namely you forgot a factor of 4 when expanding brackets).