10
$\begingroup$

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct families. Would it be acceptable to call the complexity of an algorithm $O(n * m)$ or $O(n + m)$ (depending on if we use a naive or an optimized algorithm)?

On a similar vein, let us presume the algorithm we choose actually requires two stages - a setup phase on the first string which allows us to process any number of other strings without incurring that initial cost. Would it be considered appropriate to say it has a $O(n)$ construction followed by any number of $O(m)$ calculations?

Would it be appropriate to just call them $O(n)$ because both calculations are linear?

$\endgroup$
  • $\begingroup$ See the comments on this answer for a little background - my respect to @corsiKa for so bravely asking such a contentious question. $\endgroup$ – OldCurmudgeon Sep 15 '14 at 23:25
  • $\begingroup$ @OldCurmudgeon, I see. I would hate to wade into that comment thread. Oldcurmudgeon, are you arguing over big-O notation without understanding big-O notation? Awkward indeed. Also, you and corsiKa are arguing over running time without defining the parameters $n$ and $m$ -- a recipe for miscommunication. Hint: one common convention when dealing with strings is to agree to use $m$ to use the length of one string and $n$ for the length of another string -- but ideally it's probably best to make this explicit, because otherwise it can cause confusion (as illustrated here). $\endgroup$ – D.W. Sep 15 '14 at 23:40
  • $\begingroup$ @D.W. It's possible that OldCurmudgeon simply learned a different definition in school... as I point out in a comment below, it's possible to eschew multiple variables, though I've never really thought about doing it until now. Maybe this - or something like it - used to be standard? $\endgroup$ – Patrick87 Sep 16 '14 at 6:34
  • 2
    $\begingroup$ I think this has sufficient answers here and here. $\endgroup$ – Raphael Sep 16 '14 at 8:22
13
$\begingroup$

Yes, of course. This is fine and perfectly acceptable. It is common and standard to see algorithms whose running time depends upon two parameters.

For instance, you will often see the running time of depth-first search expressed as $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. This is perfectly valid. The meaning of this is there exists a constant $c$ and numbers $n_0,m_0$ such that the running time of the algorithm is at most $c \cdot (n+m)$, for all $n>n_0,m>m_0$. In other words, if the exact running time is $f(n,m)$, we say that $f(n,m) = O(n+m)$ if there exists $c,n_0,m_0$ such that $n>n_0$ and $m>m_0$ implies $f(n,m) \le c \cdot (n+m)$.

Yes, it is perfectly appropriate and acceptable to say that the first stage takes $O(n)$ time and the second stage takes $O(m)$ time.

Important: make sure you define what $n$ and $m$ are. You can't say "this is an $O(n)$ time algorithm" without specifying what $n$ is. If $n$ isn't specified in the problem statement, you need to specify it. For instance, see graph algorithms, where we typically define $n = $ # of vertices and $m = $ # of edges.

As far as whether you can call them $O(n)$ time, no, of course not -- unless you somehow know that $m = O(n)$. Of course, if you know that $m = O(n)$, then it follows that $m+n = O(n)$, so an $O(m+n)$ time algorithm is also an $O(n)$ time algorithm. But if there is no guarantee that $m = O(n)$, then you cannot call it an $O(n)$ time algorithm.

This is basic stuff. You'll find it all over algorithms textbooks.

$\endgroup$
  • 1
    $\begingroup$ @OldCurmudgeon, odds are that you'll find examples of this in many standard algorithms textbooks. What ones have you looked at? Have you tried looking at the chapter on depth-first search (the example that I mentioned in my answer)? $\endgroup$ – D.W. Sep 15 '14 at 23:41
  • 2
    $\begingroup$ @OldCurmudgeon In my edition of CLRS exercise 3.1-8 presents exactly this definition of the $O$-notation for functions of many variables. And its upper bound on the running time of dfs is $O(V+E)$ for a graph $(V,E)$. $\endgroup$ – Kirill Sep 16 '14 at 6:07
  • 2
    $\begingroup$ @Kirill My point was that it's conceivable, at some point in the past, it was considered customary to only consider the total aggregate length, to the extent that doing otherwise might have been considered an error. If you we're grading a student's exam and that student used total input length $n$ as the variable for time complexity of DFS, would you consider it an error not to consider two dimensions (V and E)? What's true, and what people are willing to concede, are not always one and the same. $\endgroup$ – Patrick87 Sep 16 '14 at 7:09
  • 1
    $\begingroup$ I agree insofar as everybody uses Landau notation this way, but almost nobody knows what it actually means (unless you connect the parameters functionally). See also the article linked in A. Schulz's answer here which starts off by stating that the "basic" and "common" use is wrong. $\endgroup$ – Raphael Sep 16 '14 at 8:18
  • 1
    $\begingroup$ @Patrick87 Complexity theory uses, by virtue of the definition of many well-known classes, mostly input length (with notable exceptions). Algorithm analysis is -- when done seriously -- interested in learning something about actual resource usage (as far as the model allows) so other parameters become more interesting as to paint the whole picture (more accurately). $\endgroup$ – Raphael Sep 17 '14 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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