# If $m \leq a \log m + b$, why does $m = O(\max\{a \log a, b\})$?

I'm found this claim in something I was reading and I'm having trouble working out the logic. Can someone help me out?

• Can you confirm the $a \log m$ part? Is that $a \log a$, perhaps? – chi Jan 1 '17 at 13:15

$m \leq a \log m + b$ has no asymptotic behavior. This is because regardless of constants $a, b$, the left hand side grows faster than the right side, leaving only a finite range where $m$ is valid.
It is likely what was meant is $m \leq a \log a + b$. In this case we have that $m$ is bounded by something, so $m = O(a \log a + b)$. If you have that $O(x + y) = O(\max(x, y))$, then the question is solved.
But why is $O(x + y) = O(\max(x, y))$ true? With big-$O$ notation we are interested in the asymptotically fastest growing part. We ignore constant factors. Now check three cases (in the limit):
$$x < y \rightarrow O(x + y) = O(y)$$ $$x > y \rightarrow O(x + y) = O(x)$$ $$x = y \rightarrow O(x + y) = O(x + x) = O(2x) = O(x)$$
Since our choice for $x = y$ doesn't matter, we can see that choosing the minimum gives us the right asymptotic behavior.
• Since the result is $O(\max(a\log a, b))$ is guess that $a,b$ are not constants. It's not entirely clear, though. – chi Jan 1 '17 at 19:17