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.

(My apologies if this is a duplicate; I did some searching but didn't turn up anything else like this on the site. Please let me know if it's a duplicate and I'll gladly delete it.)

I was reading up on various graph algorithms (Dijkstra's algorithm and some variants) and found the runtime $O(m + n \log n)$, where $m$ is the number of edges in the graph and $n$ is the number of nodes. Intuitively, this makes sense, but I recently realized that I don't know, formally, what this statement means.

The definition of big-O notation that I am familiar with concerns single-variable functions; that is, $f(n) = O(g(n))$ if $\exists n_0, c$ such that $\forall n > n_0. |f(n)| \le c|g(n)|$. However, this definition doesn't make sense for something like $O(m + n \log n)$, since there are two free parameters here - $m$ and $n$. Although in the context of graphs there are well-specified relations between $m$ and $n$, in some other algorithms (for example, string matching) the runtime might be described as $O(f(m, n))$ where $m$ and $n$ are completely independent of one another.

My question is this: what is the formal definition of the statement $f(m, n) = O(g(m, n))$? Is it a straightforward generalization of the definition for one variable where we give lower bounds on both $m$ and $n$ that must be simultaneously satisfied, or is there some other definition defined in terms of limits?

Thanks!

share|improve this question
1  
This is pretty well explained in wikipedia and papers like On Asymptotic Notation with Multiple Variables –  Mark Beadles Jan 6 '12 at 1:54
1  
@MarkBeadles- Wow, I feel silly... I completely missed that section. Thanks for spotting that! If you promote that link to an answer, I can accept it to mark the question closed. –  templatetypedef Jan 6 '12 at 1:57
    
Will do, glad to help. –  Mark Beadles Jan 6 '12 at 2:02

1 Answer 1

up vote 3 down vote accepted

Bachman-Landau big O and similar notation for multiple variables is pretty well explained in the wikipedia article on big O notation, as well as papers like On Asymptotic Notation with Multiple Variables.

share|improve this answer
    
I don't think this fundamentally answers the question as it is "barely more than a link to an external site". –  Pål GD Dec 17 at 16:32

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.