1
$\begingroup$

Assume $\epsilon$ is a small positive parameter, $0 < \epsilon <<1$, $k$ is another parameter (the size of which we don't know), and $B_{1}$ and $B_{2}>1$ are constants. Suppose I have a quantity $\Delta t$ satisfying the inequalities $B_{2} \epsilon \leq \Delta t \leq B_{1}k$.

Now assume I have some other quantity, call it $Q$, such that $Q \sim O((\Delta t)^{2} + \epsilon \Delta t)$. Do the above inequalities imply that I can write

$$O((\Delta t)^{2} + \epsilon \Delta t) \sim O(k^{2})$$

?

$\endgroup$
  • $\begingroup$ Should $Q$ have something to do with $k$? I don't see where $k^2$ came into the picture. $\endgroup$ – Ian Jan 18 '17 at 23:54
  • $\begingroup$ Well, I can see that since $\Delta t \leq B_{1}k$, we can say $(\Delta t)^{2} \leq B_{1}^{2}k^{2}$, is that what you mean? @Ian $\endgroup$ – Alex Jan 18 '17 at 23:57
  • $\begingroup$ Sure, $Q\sim O(k^2)$. You can prove this directly with algebraic manipulation. $\endgroup$ – Matt Samuel Jan 18 '17 at 23:59
  • $\begingroup$ Thanks! I'd be grateful if you could provide a few more details though @MattSamuel $\endgroup$ – Alex Jan 19 '17 at 0:00
1
$\begingroup$

$$(\Delta t)^2\leq B_1^2k^2$$ $$\epsilon\leq\frac{B_1}{B_2}k$$ $$\epsilon\Delta t\leq \frac{ B_1^2}{B_2}k^2$$ Sum the first and the third inequalities to finish the proof.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.