Algorithm - How to show Big O for 2 functions
Interpreting lg(n) as log2(n), set n=2^x so that the inequality transforms to

ln(2)*x &lt;= 2^sqrt(2*x)


Now apply the square root,

sqrt(2*ln(2)) * sqrt(x/2) &lt;= 2^sqrt(x/2)


and we are left to prove that for y&gt;0

2^y/y &gt; sqrt(2*ln(2))


Indeed, the minimum of the left side can be found for 0=ln(2)*y-1 or y=1/ln(2) with minimum value 2^(1/ln(2))*ln(2). Numerically, the gap between 1.88416938536372 and 1.1774100225154747 is large enough to exclude any floating point errors. Thus all the equivalent inequalities including the original one are true.