patternMajor
Is O(mn) considered "linear" or "quadratic" growth?
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.
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.