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?


1 Answer 1


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)$

  • $\begingroup$ 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. $\endgroup$
    – zkutch
    Sep 14, 2021 at 7:58
  • $\begingroup$ @zkutch oops! I have made the edit. Also, please feel free to edit the answer. $\endgroup$
    – D Goyal
    Sep 14, 2021 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.