# Is O(mn) considered “linear” or “quadratic” growth?

If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (since it's a product of two sizes)? Or something else?

I feel calling it "linear" is confusing because O(m + n) is also linear but much faster, but I feel like calling it "quadratic" is also weird because it's linear in each variable separately.

• It is important to say linear in what. If, for example, we have a graph with $m$ edges and $n$ vertices, $O(m+n)$ is linear in the number of edges, but (potentially) quadratic in the number of vertices. – Raphael Feb 6 '13 at 7:43
• I think Raphael's comment is spot on. "Linear" must be used relative to something, often the size of the input. If you're transposing an $m\times n$ matrix $O(mn)$ is "linear" since the input has size $O(mn)$. If you're searching for occurrences of an $n$ character string in an $m$ character string, $O(mn)$ is not linear---$O(m + n)$ would be. – SamM Feb 7 '13 at 1:54
• I would agree with @Raphael's comment too, but at the same time it's not uncommon to hear people say a particular time complexity is "linear" without mentioning relative to what. And in some cases it doesn't matter, e.g. O(m + n) is linear relative to all the inputs, so I wouldn't think twice about calling it linear as SamM also did above. But that begs the question: what, if anything, makes O(mn) not linear? – user541686 Feb 7 '13 at 19:01
• @Mehrdad: I think the baseline is "in the input size, assuming the input is encoded as binary string (on a Turing machine tape)". This input size is then a function of $n$ and $m$ itself. SamM gives good examples. – Raphael Feb 7 '13 at 19:14
• See also people.cis.ksu.edu/~rhowell/asymptotic.pdf on landau notation in multiple variables. – Jonas Kölker Feb 8 '13 at 19:11

In mathematics, functions like this are called multilinear functions. But computer scientists probably won't generally know this terminology. This function should definitely not be called linear, either in mathematics or computer science, unless you can reasonably consider one of $m$ and $n$ a constant.

• What makes considering one of $m$ and $n$ a constant reasonable? – user2768 Nov 7 '18 at 17:09
• @user2768 constants are dropped – csguy Jan 2 at 3:45
• @csguy Yes, but what makes it reasonable to consider them constants? Perhaps a better wording would be unless m or n are constants. – user2768 Jan 6 at 8:41
• @csguy: Example: If somebody designs an $O(mn)$ algorithm for strings of length $n$ with $m$ different symbols, and somebody else wants to use it for strings of English text, then for that second person it is a linear-time algorithm. – Peter Shor Jan 6 at 12:44

To elucidate on the discussion in the comments, it matters what you're measuring growth relative to.

As mentioned by @Kaveh, $O(mn)$ is not linear in both at the same time, but is linear if one is a constant and the other one grows.

On the other hand, $O(m+n)$ would likely be considered linear. Intuitively, if $m$ doubles, or if $n$ doubles, or even if both $m$ and $n$ double, $m+n$ cannot more than double. This is not true of $mn$; if $m$ and $n$ both double $mn$ goes up by 4. This is why in many contexts this running time would be considered quadratic. I give an example of this with string matching in a couple paragraphs.

But usually when you're using Big-$O$ notation, you're using it in reference to something in particular. Since we're mostly theorists, it's generally the size of the input to the problem.

Let's take Matrix Addition, for example. Adding two $m\times n$ matrices takes $O(mn)$ time. But each element of our input is only touched once, so this would usually be called linear. Put in other words, our input is of size $O(mn)$, so a running time of $O(mn)$ is linear in the size of the input.

Now let's look at string matching--namely, we are given a string of size $m$ and a string of size $n$ and we want to see if there is an occurrence of the smaller string within the bigger string. We can check this naively in $O(mn)$ time; this would generally be considered quadratic. Why? If $m$ and $n$ can be anything, set $m = n$. Then our running time is $O(m^2)$ and our input is of size $2m$.

On the other hand, if we use the Rabin-Karp algorithm, we get (on average) $O(m+n)$ time. Our input consisted of both strings, so our input was of size $O(m+n)$ as well. Therefore, this would generally be referred to as linear.

To sum up: $O(mn)$ is generally called linear for things like matrix multiplication because it's linear in the size of the input, but it's generally called quadratic for things like string matching because of the smaller input. Which term is appropriate depends on the context you're using it in.

If you are measuring the running time in $(m,n)$ then $O(mn)$ is not a linear function in $(m,n)$. If there is no relation between $m$ and $n$ this function can grow quadraticly in general.

However it is a linear function in each of them separately, i.e. if you fix one of them and look at the growth in the other variable then it is a linear function in other one.

To measure the complexity of the problems with multiple inputs, one way is to find the dominant variable and then bound other inputs based on that variable. With this approach you could have the complexity function based on single variable.

• There may not be a dominant variable, for example if you have the numbers of nodes and edges. – Raphael Apr 2 '13 at 8:05

Given some Language $L = \{w_1\#w_2|w_i \in (\Sigma\setminus\{\#\})^*,\dots\}$ and a function $f$ such that $\min\{|w_1|,|w_2|\} \leq f(|w|)$ for every $w=w_1\#w_2 \in L$ you can estimate the running time of an $\mathcal O(|w_1|\cdot|w_2|)$ algorithm which recognizes $L$ as $\mathcal O(f(|w|)\cdot(|w|-f(|w|))= \mathcal O(f(|w|)|w|-f(|w|)^2)= \mathcal O(f(|w|)|w|)$.

This means you get linear time, if the smaller part of your input is constant (relative to the whole input), something in between (like $\mathcal O(n\log n)$) if it's sublinear and quadratic runtime if it's linear.