Algorithms - Solving recurrence-relations/Bounds? I'm currently in a course, and I for the life of me cannot figure out what my professor is doing. I could really use a working example, and I was hoping someone here might oblige. 

Suppose we have this recurrence:

$$    T(n) = 2T(n/2) + \log n$$

How would we figure out running time for this, and specifically, how would we PROVE the upper and lower bounds (ideally as tight as possible)?

I tried working through my homework with the help of a few YouTube videos, but I don't seem to be following it. In giving an explanation, please try and be careful to explain why something is a certain time, as I haven't really gotten the hang of intuiting that yet.

I have some working knowledge of induction and calculus, but it seems like I'm missing a big chunk of context somewhere and I really need to get up to speed. Thank you for any assistance.
First of all, a recurrence is not necessarily about the running time of anything. So you don't figure out "the running time", you solve the recurrence.

Second, your recurrence only possibly makes sense for powers of 2, and even then, it needs a base case. I'll assume that $T(1) = C$.

You can use the master theorem to solve your recurrence, but you can also do it directly. First you expand it (for simplicity, I'm assuming the base of the logarithm is 2):
$$
\begin{align*}
T(2^k) &amp;= k + 2T(2^{k-1}) \\ &amp;=
k + 2(k-1) + 4T(2^{k-2}) \\ &amp;=
k + 2(k-1) + 4(k-2) + \cdots + 2^{k-1}(k-(k-1)) + 2^k T(1) \\ &amp;=
(1+2+\cdots+2^{k-1})+(1+2+\cdots+2^{k-2})+\cdots+(1) + 2^k C \\ &amp;=
(2^k-1)+(2^{k-1}-1)+\cdots+(2-1)+(1-1) + 2^kC \\ &amp;=
(2^k+\cdots+1)-(k+1) + 2^kC \\ &amp;=
2^{k+1}-k-2 + 2^kC.
\end{align*}
$$
If you want to be very pedantic, you can prove this by induction. In terms of $n=2^k$, this reads
$$
T(n) = (2+C)n-\log n - 2 \sim (2+C) n.
$$
In particular, $T(n) = \Theta(n)$. You could also get this conclusion from case 1 of the master theorem.