2

I have a function $f(m,n)$ for which there exists a constant $\alpha<2$ such that, for fixed $m$, as $n\rightarrow\infty$, we have $f(m,n)\leq\alpha\sqrt{m/n}$, and for fixed $n$, as $m\rightarrow\infty$, we also have $f(m,n)\leq\alpha\sqrt{m/n}$. Is there a proper concise way to express this using big O notation?

Lyly Truong
  • 23
  • 2
  • Your description is clear to me but if you want to use big O notation then you could say something like $$``f(m,n) = O\left(\sqrt{m/n}\right)$$ as $m \to \infty$ with $n$ fixed or as $n \to \infty$ with $m$ fixed." It might be worth trying to find out if you can combine these conditions into a stronger statement like "as $mn \to \infty$" as well. – Antonio Vargas Sep 03 '13 at 07:01

1 Answers1

0

Perhaps you meant to say that $\alpha$ depends on $m$ in the first case and $n$ in the latter, but it doesn't matter since $\alpha \lt 2$, we have $f(m,n) \le 2 \cdot \sqrt{\frac{m}{n}}$ or $f(m,n) = O(\sqrt{\frac{m}{n}})$.

Dan Brumleve
  • 17,796
  • Yes, but this is only valid if we fix one, and take the limit as the other approaches infinity, so I don't think it's accurate to say that $f(m,n) = O(\sqrt{m/n})$ – Lyly Truong Sep 03 '13 at 04:35
  • @Lyly, I think OP meant to say something like: for all $m$ there exists an $\alpha \lt 2$ such that for all $n$ we have $f(m,n) \le \alpha \cdot \sqrt{\frac{m}{n}}$ [and the same with $m$ and $n$ switched in the quantifiers but not in the expression]. – Dan Brumleve Sep 03 '13 at 04:38
  • @Lyly I just realized you are OP, is that what you meant? You say "as $n \rightarrow \infty$" but then follow it with an inequality involving $n$ so I thought you must have meant "for all $n$". – Dan Brumleve Sep 03 '13 at 04:50
  • Thanks Dan, but I really meant the expression exactly as written. It's a statement about the limiting behavior as one of the variables becomes large. – Lyly Truong Sep 03 '13 at 05:37
  • But what you have written isn't clear. When you say "as $n \rightarrow \infty$" do you mean something like "there exists an $n_0$ such that for all $n \gt n_0$"? Even in that case I think my answer is correct. – Dan Brumleve Sep 03 '13 at 05:42
  • Yes, that's right, I should have added the bit about $m_0$ and $n_0$. However it doesn't seem right to me to just state that $f(m,n) = O(\sqrt{m/n})$ because, for example, I don't know anything about the behavior of the function when both $m$ and $n$ become large. – Lyly Truong Sep 03 '13 at 05:45
  • @Lyly I think in this case it is more of an extension than an abuse of the notation. But without the $\alpha \lt 2$ constraint it doesn't always make sense. – Dan Brumleve Sep 04 '13 at 08:24