# Interpretation of an asymptotic notation

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?

• Closely related reference questions: cs.stackexchange.com/q/3149/98, cs.stackexchange.com/q/9523/98 – Raphael Sep 4 '19 at 6:28
• 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!). – Raphael Sep 4 '19 at 6:30
• 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. – Raphael Sep 4 '19 at 6:32

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.
• 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? – user91015 Apr 6 '19 at 22:15