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

Question

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$"?

Answer 1

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)$.