$$T(n)=2T\left(\frac{n}{2}\right)+6n+\log(n)$$
Using the master theorem is seems to be both in case $2$ and case $3$.
Is there another way to approach this?
I tried this:
$$T(n)=2\cdot 2\cdot (2T\left(\frac{n}{8}\right)+\frac{6}{8}n+\log(n)-\log(4))+3n+\log(n)-\log(2)+6n+\log(n)$$
Best Answer
Similarly to this and this, we have: $$T(n)=2T\left(\frac{n}{2}\right)+6n+\lg n,\quad \ \lg n=\log_2 n$$ $$2T\left(\frac{n}{2}\right)=2\left(2T\left(\frac{n}{2^2}\right)+6\frac{n}{2}+\lg \frac{n}{2}\right)=2^2T\left(\frac{n}{2^2}\right)+6n+2\lg\frac{n}{2}$$ $$2^2T\left(\frac{n}{2^2}\right)=2^2\left(2T\left(\frac{n}{2^3}\right)+6\frac{n}{2^2}+\lg \frac{n}{2^2}\right)=2^3T\left(\frac{n}{2^3}\right)+6n+2^2\lg\frac{n}{2^2}$$ $$\dots$$ $$2^{q-1}T\left(\frac{n}{2^{q-1}}\right)=2^qT\left(\frac{n}{2^q}\right)+6n+2^{q-1}\lg \frac{n}{2^{q-1}}$$ We now consider the limit condition $$T\left(\frac{n}{2^q}\right)=T(1)\Rightarrow \frac{n}{2^q}=1\Rightarrow n=2^q \Rightarrow q=\lg n$$ Note that we only iterated the first term, of $T(n)$ and when we combine it back, we mustn't forget about the second and the third one. $$T(n)=2^{\lg n}T(1)+\sum_{k=0}^{q-1} 6n+\sum_{k=0}^{q-1} 2^k\lg \frac{n}{2^k}$$ $$=n \cdot T(1) +6n \cdot \sum_{k=0}^{q-1} +\sum_{k=0}^{q-1} 2^k(\lg n- \lg 2^k)$$ $$=n\cdot \Theta(1)+6n\cdot q+\lg n \sum_{k=0}^{q-1} 2^k -\sum_{k=0}^{q-1} 2^k \cdot k$$ Now using this formula and $q=\lg n$ we get: $$T(n)=\Theta(n)+6n\lg n+\lg n (2^q -1) -(q-1)2^{q+1}+q2^{q}-2$$ $$=\Theta(n)+6n\lg n +\lg n (n-1) -(\lg n-1) 2\cdot n +\lg n \cdot n -2$$ And since constants doesn't matter, we simply get: $$T(n)=\Theta(n\lg n)$$
Hopefully I haven't done any calculation mistakes, but this is a way to do it.