(solved)Prove that for any constant k, log^k (N) = O(N)

We can easily prove using calculus [scroll down for the proof]:

$\displaystyle \ln x < x, x \geqslant 1$

Put $\displaystyle x= N^{(1/k)}$

$\displaystyle \therefore \ln {(N^{(1/k)})} < N^{(1/k)}$

$\displaystyle \implies \frac 1k \times \ln {N} < N^{(1/k)}$

$\displaystyle \implies \bigg(\frac 1k \times \ln {N}\bigg)^k < N$

$\displaystyle \implies \bigg(\frac 1k \times \ln b \cdot \log_b {N}\bigg)^k < N$

$\displaystyle \implies \log_b ^k {N}< \frac{k^k}{ (\ln b)^k} \times N$

$\displaystyle \implies \log^k {N} = O(N)\:\text{QED}$

consider $\displaystyle g(x) = x - \ln x$

$\displaystyle \implies g'(x) = 1 - \frac 1x$

$\displaystyle \implies g'(x) \geqslant 0, x \geqslant 1 $

$\displaystyle \implies g(x)$ is increasing

but $\displaystyle g(1) \gt 0$

$\displaystyle \implies x - \ln x \gt 0, x \geqslant 1$

transposing, $\displaystyle \ln x \lt x$ proved!