Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no algorithm that solves the given problem in $o(m + \log{n})$?

In particular, does it mean that an $O(\log{n})$ algorithm is possible?

  • $\begingroup$ Closely related reference questions: cs.stackexchange.com/q/3149/98, cs.stackexchange.com/q/9523/98 $\endgroup$ – Raphael Sep 4 '19 at 6:28
  • $\begingroup$ Basically, nobody really agrees on how to formally define and/or interpret multi-variable Landau notation; it doesn't really work the way we want it to. If your prof uses the notation, ask them for a formal definition (not how the one you were probably given for a single parameter doesn't immediately carry over!). $\endgroup$ – Raphael Sep 4 '19 at 6:30
  • $\begingroup$ In any case, you'll have to fix the cost measure for the statement to be meaningful. Probably you mean "time"? In that case, the statement would translate to "the time-complexity of this problem is $\Omega(m + \log n)$, with the intended interpretation of that linear effort in $m$ is required, which would rule out $O( \log n)$-time algorithms. $\endgroup$ – Raphael Sep 4 '19 at 6:32

What this means is:

For every algorithm solving the problem, it is not the case that the worst-case running time $T(m,n)$ in terms of $m,n$ satisfies the following property: for every $c > 0$ there is $m_0(c)$ such that for all $n \geq m \geq m_0(c)$, $$ T(m,n) < c(m + \log n). $$

This doesn't rule out an $O(\log n)$ algorithm, since $\log n$ doesn't satisfy the property written above.

| cite | improve this answer | |
  • $\begingroup$ Let us further assume that when $m \le \log{n}$ there is no algorithm with $o(\log{n})$ time, and when $m \ge \log{n}$ there is no algorithm with $o(m)$ time. According to the above definition, this is not equivalent to saying that there is no $o(m+\log{n})$ algorithm. So what can we say about the complexity in this case? In many cases, I saw that this leads to a conclusion that there is no $o(m+\log{n})$ algorithm, or that any algorithm requires $\Omega(m+\log{n})$. What is the correct interpretation for such cases? $\endgroup$ – user91015 Apr 6 '19 at 22:15
  • $\begingroup$ There is no single correct interpretation. When in doubt, check the proof to see what exactly is proved. If it is a conjecture or hypothesis, it ought to be spelled out in full. $\endgroup$ – Yuval Filmus Apr 7 '19 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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