$g(n)=\omega (1)$ then for every $k∈\mathbb{N} $ implies $g(n^{k+1}))-g(n^k)= \Theta(g(n^{k+1}))$?

41 Views Asked by At

$g(n)=\omega (1)$ then for every $k∈\mathbb{N} $ implies $g(n^{k+1}))-g(n^k)= \Theta(g(n^{k+1}))$

when $g: \mathbb{N} \to \mathbb{R}+$

ps: $g(n)=\omega (1)$ means that for evert $k>0$ there is a $m>0$ that for every $n>=m$ we get $g(n)>=k*1$ or in other words $ \lim_{n\to \infty} 1/g(n)=0$

and $\Theta$ is big theta notatin

1

There are 1 best solutions below

15
On BEST ANSWER

No.

Take $g\colon \mathbb{N}\to [0,\infty)$ defined by $g(n) = \log\log n$ for $n\geq 10$ large enough (and $g(n)=1$ for $n< 10$). (This is a technically to make sure $g>0$ even for small $n$.) Then $g(n) = \omega(1)$ as required, yet, for any fixed $k\geq 1$ and $n\geq 10$, $$ g(n^{k+1}) - g(n^{k}) = \log (k+1) + \log\log n - \log k - \log\log n = \log\left(1+\frac{1}{k}\right) = \Theta(1) $$ while $$ g(n^{k+1}) = \log (k+1) + \log\log n = \omega(1)\,. $$