Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
5  
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
2  
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
2  
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? –  Mehrdad Feb 7 '13 at 19:01
2  
@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
    
@SamM I think the first three comments together amount to a new answer. Would you do the honors? –  Raphael Feb 7 '13 at 19:16
show 2 more comments

5 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

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

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.

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