Interpretation of an asymptotic notation
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 &gt; 0$ there is $m_0(c)$ such that for all $n \geq m \geq m_0(c)$,
  $$ T(m,n) &lt; c(m + \log n). $$


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