0
$\begingroup$

Premise for context: Reading a paper I stumbled upon the following expression $$n(1+p)^{O(\log_{\sigma}n)} + 2$$ which is claimed to be $O(n)$ when $p \in O(1/\log_{\sigma}n)$, under the (reasonable) assumption that $n > \sigma$. Substituting we get $$n\left(1+O\left(\frac{1}{\log_{\sigma}n}\right)\right)^{O(\log_{\sigma}n)} + 2$$

As we are dealing with asymptotic notation I would look only at the higher order terms (this passage actually turned out to be completely wrong, have a look at the comments for details) getting to

$$n\left(1+O\left(\frac{1}{\log_{\sigma}n}\right)^{O(\log_{\sigma}n)}\right) + 2$$

Let now $x=\log_{\sigma}n$ and discard the constant to get to $$O(n)+n \cdot O\left(\frac{1}{x}\right)^{O(x)}$$

end of premise, if you like more details feel free to ask them.

To verify the claim we need to check the value of $O\left(\frac{1}{x}\right)^{O(x)}$, which should turn out to be $O(1)$ to satisfy the initial claim.

Looking at the value of $y^{-y}$ which tends to 1 for growing values of $y$ in $\mathbb{N}$ (e.g. considering $y^{-y} = e^{-y\cdot \log y }$ and seeing that the value $y\cdot \log y$ goes to $\infty$).

This seems correct to me but I was wondering if my (not so formal) reasoning holds or not and whether there is a better line of reasoning to verify this.

$\endgroup$
2
  • 1
    $\begingroup$ It's not true that $(1+f(n))^{g(n)} = O(1+f(n)^{g(n)})$. (For one thing, increasing $g(n)$ makes the left side increase, but makes the right side decrease when $f(n)<1$.) In this case (and often when dealing with functions in exponents), I recommend writing $(1+p)^{O(g(n))} = \exp( g(n)\log(1+p) )$ and finding an upper bound for $g(n)\log(1+p)$ as an intermediate step; here you should be able to prove that it's $O(1)$. $\endgroup$ Sep 14, 2023 at 21:39
  • 1
    $\begingroup$ Start by $1 + p \le {\rm e}^p$ for $p\ge 0$. $\endgroup$
    – Gary
    Sep 15, 2023 at 4:05

1 Answer 1

1
$\begingroup$

As $n\to\infty$, $$n(1+p)^{O(\log_{\sigma}n)}=\exp\left(\ln\left( n\right)+O(\log_{\sigma}n)\ln(1+p)\right)=n\exp(O(\log_{\sigma}n)\ln(1+p))$$ substitue as you did, but note that by Taylor's formula, $$\ln(1+O(1/\log_\sigma n))\sim O(1/\log_\sigma n)$$ as $n\to\infty$, then using the fact that $e^{O(1)}=O(1)$, i.e., it is bounded, $$n\exp(O(1))=O(n)$$ as $n\to\infty$. As you have noticed, discarding the constant $2$ which is $O(1)$ doesn't matter here.

$\endgroup$
4
  • $\begingroup$ Writing $\exp(O(1))\sim 1+O(1)$ does not make much sense. Just note that $\exp(O(1))$ is a bounded quantity, i.e., it is $O(1)$. $\endgroup$
    – Gary
    Sep 15, 2023 at 7:05
  • $\begingroup$ @Gary. You are right, $e^{O(1)}$ is just a number. I will edit that. $\endgroup$
    – bob
    Sep 15, 2023 at 7:06
  • $\begingroup$ Thanks a lot. In place of Taylor's formula I think we can also use the simpler obesrvation $log(1+x) \le x$ s.t. $x > -1$ (which holds since $x = O(1/\log_{\sigma}n) \ge 0$ in our case) in this case as we are looking for an upper bound right? $\endgroup$
    – De Costa
    Sep 15, 2023 at 7:48
  • $\begingroup$ @DeCosta. Yes, I think it is essentially the same. $\endgroup$
    – bob
    Sep 15, 2023 at 7:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .