0

I do not know if it is the usual type of question to ask for someone to confirm a computation, but I don't really have any way to know if this is correct (or do I?).

Lemma A function $f: \mathbb{N} \to \mathbb{C}$ verifies $$f(n) \leq \frac{1}{\tfrac{1}{n^3}+O(\tfrac{1}{n^5})}\log{\left(\frac{(1 - \varepsilon)(n+O(\tfrac{1}{n}))}{O(1)}\right)}$$ for $ \varepsilon > 0$.

I would like to simplify the bound for $f(n)$ and this is what I did:

\begin{equation} \begin{split} f(n) & \leq \left(n^3 + O(n)\right) \log{\left(n\frac{(1 - \varepsilon)(1+O(\tfrac{1}{n^2}))}{ O(1)}\right)} \\ & = \left(n^3 + O(n)\right) \left[\log{(n)}- \log{\left(\frac{O(1)}{(1 - \varepsilon)(1+O(\tfrac{1}{n^2}))}\right)}\right]\\ & = n^3 \log{(n)}+ O(n^3). \end{split} \end{equation}

Can anyone tell me if this correct or if not, tell me how to correctly simplify the expression?

Macarena Perelman
  • 73
  • Careful: $\log{O(1)}$ is $\leq O(1)$, not “in” $O(1)$ (you need $\log{\Theta(1)}$. For instance, what happens if this $O(1)$ in the log is $e^{-e^n}$? – Aphelli Sep 29 '21 at 21:26
  • what do you mean? – Macarena Perelman Oct 03 '21 at 06:10
  • Define $f_0(x)=\frac{1}{1/n^3+0}\log{\frac{(1-\epsilon)(n+0)}{e^{-e^n}}}$. Does $f_0$ satisfy your constraints? Yes. Does it satisfy your final inequality? No. – Aphelli Oct 03 '21 at 11:17

0 Answers0