# What is a/O(a)?

I have an algorithm where one parameter is defined as $$p = O(a^{2}\ln(b/c))$$, where $$a,b,c$$ are positive numbers. In the proof of the convergence rate one step goes as follows:

$$16a\sqrt{\frac{\ln(b/c)}{p}}+\frac{1}{16} \leq \frac{1}{4}$$

What exactly do i substitute for the value of p to arrive at $$\frac{1}{4}$$? If I use $$p = a^{2}\ln(b/c)$$ I get: $$16 + \frac{1}{16} \leq \frac{1}{4}$$, which is obviously not correct.

From the data you have given us, it is impossible to deduce $$16a\sqrt{\frac{\ln(b/c)}{p}}+\frac{1}{16} \leq \frac{1}{4}$$

For two reasons:

1. $$p=O(\ldots)$$ sets an upper bound on $$p$$, whereas your inequality reauires a lower bound on $$p$$ (because it is in the denominator).
2. In any case, the $$O(\ldots)$$ notation only tells us about the limiting behaviour as $$a,b,c$$ tend to infinity; whereas your inequality claims to be true for all $$a,b,c$$.

So you need to tell us the whole story. Or perhaps you have simply misunderstood the algorithm.

• There we go, I'm seeing my naïveté already. May 15, 2019 at 23:33
• Could this be related to my answer where I squared both sides? If I'm thinking of algebra correctly, doing such with an inequality would require more analysis of the signs involved, possible different paths (depending on whether or not both sides of the equality are known to be positive), and possible implications that flip the inequality sign. I want to analyze how these concepts relate to the idea of upper and lower bounds. May 16, 2019 at 0:10
• It looks like you are right, since it is impossible to get this inequality with the given value of p. It seems that the value of p just has to be $p \geq \frac{16^{4}a^{2}\ln(b/c)}{9}$. But thank you for the clarification of the $O(...)$ notation. May 16, 2019 at 13:54

Here's my analysis. I'm new here, and mathematics is more of a hobby for me. Still, this seems like a good place to start.

$$16a\sqrt{\frac{\ln(b/c)}{p}}+\frac{1}{16} = \frac{1}{4}$$

subtract $$1/16$$ from each side to arrive at

$$16a\sqrt{\frac{\ln(b/c)}{p}} = \frac{3}{16}$$

square both sides to obtain the next equality. (Note that I'm not sure about this part of the whole business. You have stated that $$a$$, $$b$$, and $$c$$ are positive integers, but we don't know how $$b$$ and $$c$$ relate. For example, is $$b < c$$, or more importantly is $$(b/c) \lt e$$ ? Note that, having a background in physics, I've denoted $$e$$ as the base of $$\ln$$ , but considering you're working on an algorithm, I imagine your $$e = 2$$ and not necessarily Euler's constant.)

$$16^2 a^2 \frac{\ln{(b/c)}}{p} = \frac{9}{16^2}$$

Divide and multiply to get $$p$$ by itself, and you end up with

$$p = \frac{16^4 a^2 \ln{(b/c)}}{9}$$

I realize that it's very probable that this is a naïve answer, with the concerns about a negative radicand that I stated and concerns about $$p$$ being a function of $$a$$, $$b$$, and $$c$$, but you said

• I want to think more about the possible negative radicand problem, though I don't know how germane it is to your problem. If we have $b=c$, p will be zero, and indeed we won't have an equality, since the initial expression will go to $1/16 \leq 1/4$ . $b=c$ will not give us an equalitiy. So, now let's look at $b < c$ , which will give us the negative radicand. Now, defining $r := \ln{(b/c)}$ , $r < 0$. Our initial equality will then be $16 a \frac{\sqrt{r} i}{\sqrt{p}} - \frac{1}{16} \leq \frac{1}{4}$. The meaning of that for your problem? I don't know. Is there complex order of complexity? May 14, 2019 at 23:31
• This answer just ignores the $O(\ldots)$ operation, which is really the source of the problem. May 16, 2019 at 10:04