# Is it legitimate to write nested big-Os in an asymptotic formula for a multivariable function?

Suppose I have a 2-variable function $g(k,n)$ and I know that $g(k,n)=O(n^{f(k)})$, for fixed $k$ as $n \rightarrow \infty$, for some function $f=f(k)$. Suppose I also know that $f(k)=O(\log k)$.

Is it legitimate to write $g(k,n)=O(n^{O(\log k)})$?

-
There are some problems with multiple-variable big-O notation when you work with 'weird' functions. I've read a paper, on the arXiv I think about this; anyone remember this? I don't have a reference ATM. :( – Charles Nov 14 '10 at 2:49
I found something like that via google: "On Asymptotic Notation with Multiple Variables". Is that what you mean? – Douglas S. Stones Nov 14 '10 at 2:58
Yes, that's it. The paper directly addresses your question, showing examples of when the notation can fail. Having said that, it's fine for 'nice' functions AFAIK, and in any case it's very common (e.g. in graph algorithms). – Charles Nov 14 '10 at 21:28

In this particular case, you can simplify and conclude that $g(k,n) = n^{O(\log k)}$, since you can put fold the first constant into the second (as long as $n,k \geq 1 + \epsilon$). This fails if you think of $n$ as tending to infinity, but $k$ could be arbitrarily close to $1$.

EDIT: My answer assumes that the constant in $g(k,n) = O(n^{f(k)})$ doesn't depend on k, which is the usual convention in computer science. If it does, we'd write $g(k,n) = O_k(n^{f(k)})$ to emphasize this (or sometimes just emphasize it in words).

-
This is false. Take g(k, n) = 2^k n^{log k} and f(k) = log k. – Qiaochu Yuan Nov 14 '10 at 3:10
@Qiaochu The constant in $O(n^{f(k)})$ cannot depend on $k$! If it does, it's better to write $O_k(\cdot)$. – Yuval Filmus Nov 14 '10 at 3:13
whoops. I seem to have slightly misread the problem. – Qiaochu Yuan Nov 14 '10 at 12:21

No (if you mean what I think you mean by that statement). If you have more than one variable in play it's always a good idea to keep track of which variables the implied constant for each big-O depends on. In your example, the implied constant for the outer big-O depends on $k$, but the implied constant for the inner big-O doesn't, so it seems misleading to use notation which pretends they are the same. And if the implied constant grows fast enough, the final statement you want is false (if an unadormed big-O means it doesn't depend on any of the variables which appear on the LHS). Consider, as I said in my comment to Yuval Filmus, $g(k, n) = 2^k n^{\log k}, f(k) = \log k$. In addition to $f(k) = O(\log k)$ you need to know that the implied constant doesn't depend on $n$.

Edit: The above was nonsense. Actually you are fine. You have a constant $C_1$ such that $f(k) \le C_1 \log k$ and another constant $C_2$ such that $g(k) \le C_2 n^{f(k)}$, hence $g(k) \le C_2 n^{C_1 \log k}$, or as Yuval Filmus points out, $g(k) = n^{O(\log k)}$.

-
As I mention in my edited post, this is a matter of convention (that the constant depends only on the "main" variable unless otherwise noted), at least when analyzing algorithms. – Yuval Filmus Nov 14 '10 at 3:18

It is legitimate provided you interpret it in the right sense. However, I do not understand what purpose it will serve though, since (obviously) you cannot write that it is equal to $\mathcal{O}(n^{log(k)})$

$\textbf{EDIT:}$

I was reading a blog by TerryTao and he has used this notation. So I assume, you can use it provided you give the right interpretation.

http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/

-
Careful. $O(n^{2\log k})$ is strictly larger than $O(n^{\log k})$. – Jeremy Hurwitz Dec 16 '10 at 18:02