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

for 1 &lt; i &lt; n do { 
  for 1 &lt; j &lt; 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$"?
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)$.