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

Prove that for any constant k, the order of growth of log^k N is linear order O(N), where O(N) is the big O notation for the linear growth order.

Categories | About Hoven's Blog


Question: Order of log^k (N)

Prove that for any constant k, $\displaystyle \log^k{N} = O(N)$

Solution in Detail
(video solution below this)

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}$

Comments and Discussion

Leave your comments on the youtube comments box.

(appendix) Proof of $\displaystyle \ln x < x, x \geqslant 1$

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!

Creative Commons License
This Blog Post/Article "(solved)Prove that for any constant k, log^k (N) = O(N)" by Parveen is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.