0

I'm somewhat convinced by taking the limits of $\frac{n}{(\log{n})^k}$ (i.e. proving little $o$ to prove big $O$), but am struggling to prove that it is the case via the formal definition; say the following:

We say that a function $f(n)$ is $O(g(n))$ if there exists a positive real number $M$ and a real number $x_0$ such that $$|f(x)|\leq M\cdot g(x)\quad {\text{ for all }x\geq x_{0}.}$$

I think it boils down to showing $(\log{n})^k \geq M\cdot n$, but I'm stumped.

David
  • 1,510
  • 1
    By definition you need to show that $(\log n)^k\leq M(\log n)$ for sufficiently large $n$. But that looks false. Take $k=2$ for example. The sequence $\frac{(\log n)^2}{\log n}=\log n$ is clearly not bounded. – Mark Aug 24 '23 at 14:03
  • This is not true. For every $f(n)$ which goes to infinity, we obviously have $(f(n))^k >> f(n)$ for all $k\ge2$, since their quotient goes to infinity. Maybe you're confusing with the location of the power? – Amit Aug 24 '23 at 14:20
  • Oops, I'm sorry! I made a typo, I wrote the title wrongly initially, but the body of the question still remains true! I'm stumped about the case $(\log{n})^k = O(n)$. – David Aug 24 '23 at 14:21
  • I see your edit now. I think you simply flipped the sides of the inequality. You actually need to show that $(logn)^k \le Mn$ for $n$ large enough. – Amit Aug 24 '23 at 14:22
  • Oh yes, many typos today. That's precisely where I'm stuck. – David Aug 24 '23 at 14:25
  • $\log(x) \in O(x)$ so $k \log(x) \in O(x)$ so $k \log(\log(x)) \in O(\log(x))$ so $\log(x)^k \in O(x)$ – Henry Aug 24 '23 at 16:14

2 Answers2

3

For any $k\in\mathbb{N}$ and $x>k+1$ we have that $x^k<k!\frac{x^{k+1}}{(k+1)!}<k!e^x$. Take $x=\log n$ and you get that $(\log n)^k=O(n)$. [Note that $k!$ is a constant.]

ancient mathematician
  • 14,102
  • 2
  • 16
  • 31
2

We have $x< e^x$. Set $x = \log(n^{1/k})$. We get $$\log(n^{1/k})<n^{1/k}$$ or, equivalently $$(\log n)^k < k^k n$$

jjagmath
  • 18,214
  • Very neat, though looser than reality. In fact $x \le e^{x-1}$ with equality only when $x=1$ so $(\log n)^k \le \left(\frac ke \right)^k n$ with equality only when $n=e^k$ – Henry Aug 24 '23 at 16:25
  • @Henry Yes, I know that the inequality is not tight. In fact, I got it by relaxing the tighter inequality $\log x \le k(x^{1/k}-1)$. – jjagmath Aug 24 '23 at 16:52