Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)})$?

share|improve this question
    
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
add comment

3 Answers 3

up vote 4 down vote accepted

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).

share|improve this answer
    
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
add comment

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)}$.

share|improve this answer
    
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
add comment

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/

share|improve this answer
1  
Careful. $O(n^{2\log k})$ is strictly larger than $O(n^{\log k})$. –  Jeremy Hurwitz Dec 16 '10 at 18:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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