22
$\begingroup$

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!

  • 1
    This is pretty well explained in [wikipedia](http://en.wikipedia.org/wiki/Big_O_notation#Multiple_variables) and papers like [On Asymptotic Notation with Multiple Variables](http://scholar.google.com/scholar?cluster=14776509847592366772&hl=en&as_sdt=0,36&sciodt=0,36)2012-01-06
  • 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.2012-01-06
  • 0
    Will do, glad to help.2012-01-06
  • 0
    this question at https://cs.stackexchange.com/questions/7480/asymptotic-analysis-for-two-variables might also help.2017-07-09

1 Answers 1