HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Is O(mn) considered "linear" or "quadratic" growth?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
linearconsideredgrowthquadratic

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#9523, answer score: 22

Revisions (0)

No revisions yet.