Time complexity of an algorithm: Is it important to state the base of the logarithm?
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant. 

If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.