New answers tagged

0

It is easy to see that $\Theta(2 +\alpha/2 - \alpha/2n) \subseteq O(2+\alpha/2) \subseteq O(1+\alpha)$ For the other direction, note that $\alpha = \frac{n}{m}$, where $m$ is the size of the table and $m \geq 1$. Therefore, $\alpha/2n < 1/2$. It gives $\Theta(2 +\alpha/2 - \alpha/2n) \subseteq \Omega(3/2+\alpha/2) \subseteq \Omega(1+\alpha)$. Therefore, $\...


Top 50 recent answers are included