1
$\begingroup$

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.

Any answer is appreciated!

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ There we go, I'm seeing my naïveté already. $\endgroup$
    – bballdave025
    May 15, 2019 at 23:33
  • $\begingroup$ 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. $\endgroup$
    – bballdave025
    May 16, 2019 at 0:10
  • $\begingroup$ 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. $\endgroup$
    – Michael W.
    May 16, 2019 at 13:54
1
$\begingroup$

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.

We're going for equality, so let's start with

$$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

any answer is appreciated

so I figured I'd give it a shot.

Please comment on anything about my answer, no matter how wrong or naïve my thoughts might be. Rip it all to pieces - that will help me learn.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – bballdave025
    May 14, 2019 at 23:31
  • $\begingroup$ Oh yeah, also, when you square both sides of an equation, you possibly introduce extraneous solutions (assuming we want a positive order of complexity. (link). There's even more fun when we allow complex numbers, but I don't imagine those being part of any <s>real</s> order of complexity for a Turing-computable answer. Please correct this if I'm wrong. $\endgroup$
    – bballdave025
    May 16, 2019 at 0:04
  • $\begingroup$ Anyway, I ignored the implications of squaring both sides on an inequality (link). Since we are interested in the equality point, the answer to "which p gives equality" can ignore these nuances, but I doubt that analysis of an algorithm can ignore them. $\endgroup$
    – bballdave025
    May 16, 2019 at 0:07
  • $\begingroup$ This answer just ignores the $O(\ldots)$ operation, which is really the source of the problem. $\endgroup$
    – TonyK
    May 16, 2019 at 10:04
  • $\begingroup$ That makes a lot of sense, @TonyK. I appreciate your comment, which helps me to learn. $\endgroup$
    – bballdave025
    May 16, 2019 at 18:42

You must log in to answer this question.

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