# The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated,

Thus, the total time required for a successful search is $$\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$$

I wouldn't have any problem if the author says the bound is eventually $$\Theta{(2+\alpha/2-\alpha/2n)}$$ or even $$\Theta{(1+\alpha(1-\frac{1}{n}))}$$. What kind of logics shall we apply to simplify the original result, i.e, cancelling the factor $$1/n$$ of $$\alpha$$. What i've missed? is anyone got the same confusion?

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, $$\Theta(2 +\alpha/2 - \alpha/2n) = \Theta(1+\alpha)$$
• Let me note, that for subsets is used "$\subset$" symbol, not "$\in$", which is symbol for belonging. Especially, when you are meaning inequalities in your reasonings. Sep 14, 2021 at 7:58