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

  • 1
    The some efficient computation that is the only part belongs to secuirty parameter $k$. – kelalaka Nov 8 at 10:24
  • 1
    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 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)$.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.