I'm not sure I should post this on the Mathematics website or the Computer science website of Stack Exchange. If I'm wrong I will replace my question.
So I'm trying to calculate the time complexity of a given algorithm. I've reached this point of the calculation and I know it's correct: $$ T(n)\leq 2+2^{h+1}(h-1). $$ Now I know I have to reach this solution: $$ T(n)\leq 2n\lg(n)+2. $$ Because this is true: $$2^{h}\leq n < 2^{h+1}.$$
I really have no idea how to get there. I think it's very easy, but for some reason I don't see it.
Taking logs of the last inequality, we see that $$h \leqslant \lg n < h+1. $$ Hence $$T(n) \leqslant 2 + 2^{h+1}(h-1)\leqslant 2 + 2^{\lg n}(\lg n - 1)= 2 + n(\lg n -1)\leqslant 2n\lg n + 2.$$