Big O complexity of $T(n)=2T(n/2)+\log(n)$

Question

I am trying to evaluate the Big $O$ complexity of $T(n)=2T(n/2)+\log(n)$. I've tried approaching it using Telescopic sum, and arrived at the following: $$T(n)=2^{k}T\left(\frac{n}{2^{k}}\right)+\sum_{i=1}^{k}2^{i-1}\log\left(\frac{n}{2^{i-1}}\right)$$ To solve this equation we can put $k=\log(n)$ and compute the order of the sum, which is equal to the following condensed product: $$\log\left(n\left(\frac{n}{2}\right)^{2}\left(\frac{n}{4}\right)^{4}\cdots\left(\frac{n}{2^{k-1}}\right)^{2^{k-1}}\right)$$ I am not able to proceed. Any hints would be appreciated. Thanks.

Answer 1

$$\log\left[\prod_{j=0}^{k-1}\left(\frac{n}{2^j}\right)^{2^j}\right]= \log\left[n^{\sum_{j=0}^{k-1}2^j}\cdot2^{-\sum_{j=0}^{k-1}j2^{j}}\right]=$$ There is an exercise for you to prove the following identity: $$\sum_{j=1}^{k}j2^j = 2^{k+1}(k-1)+2$$ Now we continue: $$=\log\left[n^{2^k-1}\cdot2^{-(2^k(k-2)+2)}\right]=(2^k-1)\log n - (2^k(k-2)+2)=$$ $$=2^k\log n-\log n - 2^k k+2^{k+1}-2= \{k=\log n\}=O(n) $$