I've been studying Sedgewick's "Algorithms" book and in proof of one proposition he writes the following:
the property is preserved because $1 + \lg i = \lg(i + i) \le \lg(i + j) = \lg k$
I cannot wrap my brain around the first part of this inequation, namely $1 + \lg i = \lg(i + i)$. Can anyone offer an explanation? Thanks in advance!
The $\mathrm{lg}$ function is the logarithm to the base $2$ (or binary logarithm), that is, $\mathrm{lg}\, 2=1$. Thus $$\mathrm{lg}\, (i+i)=\mathrm{lg} (2i)=\mathrm{lg}\, 2+\mathrm{lg}\,i=1+\mathrm{lg}\,i$$
By the way, the $\mathrm{lg}$ function can also be defined by $\mathrm{lg}\,(x)=\frac{\log x}{\log 2}$.