Skip to main content
3 votes
Accepted

Formula regarding Big-Oh (and a bit math)

Note that $\max(f, g) \leq f+g$, thus $\max(f,g) \in O(f+g)$. For the other direction, observe that $f+g \leq 2\max(f,g)$ for $f, g\geq 0$, therefore $f+g \in O(\max(f,g))$. Altogether this implies ...
BearAqua the Logician's user avatar
1 vote

Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?

After mulling this over for a long time, I've convinced myself that there is no optimal lookup complexity when insertion complexity is limited to $\mathcal O(\log\log n)$. I've written up my reasoning ...
Franklin Pezzuti Dyer's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible