# Algorithm complexity: $\mathcal O(n\cdot m)$ vs. $\mathcal O(max(n,m)^2)$

Suppose $$A(n,m,k)$$ computes

for 1 < i < n do {
for 1 < j < m do {
/* some efficient cryptographic operation */
}
}


where $$k$$ is a security parameter and integers $$n$$ and $$m$$ are upper-bound by a polynomial in that parameter.

Algorithm $$A$$ has complexity $$\mathcal O(n\cdot m)$$, which is quadratic when $$n=m$$.

Complexity nevertheless seems better than $$\mathcal O(max(n,m)^2)$$, but we've just seen it isn't.

Can we better compare algorithms with complexity $$\mathcal O(n\cdot m)$$ and $$\mathcal O(max(n,m)^2)$$?

The above captures the core aspects of my question. The details are as follows: Algorithm $$A$$ is part of a voting protocol. Integer $$n$$ represents the number of candidates and integer $$m$$ represents the number of cast ballots. So, in practice, $$n$$ is small and $$m$$ is large, which gives meaning to $$\mathcal O(n\cdot m)$$ being seemingly better than $$\mathcal O(max(n,m)^2)$$, but Big O notation looses that meaning. Is there a way to express it? I suppose we could say "the complexity of algorithm $$A$$ is linear in the number of cast ballots for small values of $$n$$", but that seems rather informal. Can we be more precise with regards to "small values of $$n$$"? Perhaps we just say "the complexity of algorithm $$A$$ is linear in $$n\cdot m$$"?

• The some efficient computation that is the only part belongs to secuirty parameter $k$. – kelalaka Nov 8 '18 at 10:24
• Actually $\mathcal O(n\cdot m)$ denotes "complexity is at most linear in $n$ and $m$" and thus I'd say $\mathcal O(n\cdot m)$ is much easier to understand and actually a better bound than $\mathcal O(\max(n,m)^2)$, because the latter tells you "if we fix $n$ and increase $m$ linearly, work wil increase quadratically" whereas the former will say that the work will grow linearly. – SEJPM Nov 8 '18 at 15:20

This type of $$\mathcal{O}$$ usage specific to the problem to indicate some other factor plays a role;
• in Bucket sort $$\mathcal{O}(n \cdot k)$$, $$k$$ is the number of buckets
• in Counting sort $$\mathcal{O}(k+n)$$, $$k$$ is the range of the inputs.
In the voting case; the $$m$$ represents the casted ballots, $$n$$ represent the candidates, and $$m \gg n$$.
• Using $$\mathcal{O}(m^2)$$ may hide some important factors especially when comparing different algorithms for the same system.
• When the candidates are very small, the algorithm will behave like linear. Using $$\mathcal{O}(m^2)$$ will hide this.
Prefer to use $$\mathcal{O}(n \cdot m)$$.