Why $T(n) = 2T(n/2) + \log n$ is in $ O(n)$?

Question

My professor said that $T(n) = 2T(n/2) + \log n$ is in $O(n)$ I checked with Master Theorem and I did not really understood why. By Case1 (which would give us exactly $O(n)$) we have

$a = 2, b = 2, f(n) = \log n$

$\log n = O(n^{\log n - c})$ for c > 0

well, if c must be > 0, then $n^0$ gives us $1$, which is constant time and $\log n$ is not in $O(1)$

Thus, I am confused how using Master Theorem we are getting $O(n)$ running time

Answer 1

Case 1 says

If $f(n) = O\left( n^{c} \right)$ where $c < \log_b a$

then:

$T(n) = \Theta\left( n^{\log_b a} \right)$.

Here $\log_b a = 1$. So we can use $c=0.99$.

Since your $f(n)$ is $\lg n$, and $\lg n = O(n^{0.99})$, the conditions are satisfied.