0
$\begingroup$

Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$

I was going through the text Introduction to Algorithms by Cormen et. al. and in the chapter dealing with hashing with collision resolved by chaining I found that the asymptotic tight bounds were just simple written just after finding the raw expression of the running time of the SEARCH algorithm. The details are as follows:


Here the authors assume that

$$m=\text{number of slots in the hash table}$$ $$n=\text{number of elements in the hash table}$$ $$\alpha=\frac{n}{m} \text{(the load factor)}$$


Theorem 1: In a hash table in which collisions are resolved by chaining, an unsuccessful search takes time $\Theta(1+\alpha)$, on the average, under the assumption of simple uniform hashing.

The expected running time is found out as $O(1) + \alpha$ which they write simply as $O(1) + \alpha=\Theta(1+\alpha)$


So first I made an attempt to show to the tight bound mathematically then try to give an intuitive logic of the same.

The authors do not quite mention here the parameter or the variable whose approach to $\infty$ defines the asymptotic behaviour. Now since the $n$ is the size of the set of keys and it is sort of the input size, I assume it as the parameter and let $\alpha = f(n)$ and by definition of $\alpha$ we have $f(n) \geq 0$

Now $c$ be the constant corresponding $O(1)$ for all $n>0$

Now let us consider the function $g(n)= 1+f(n)$,

We choose constants $\lambda,\mu >0$

We assume $c<\lambda$ and also $1<\lambda$ such that $f(n)<\lambda.f(n)$.

so we have $c+f(n)<\lambda(1+f(n)) \tag 1$

Again let us assume $\mu<c$ and $\mu<1$ such that $\mu.f(n)<f(n)$

so we have $\mu(1+f(n))<c+f(n) \tag 2$

From (1) and (2) we have , $O(1)+\alpha= \Theta(1+\alpha)$ as $\alpha=f(n)$

Now about the intuition, what I feel is that since for any $f(n)$ we have $f(n)=\Theta(f(n))$ and we do not know which is dominant: the $O(1)$ term or $\Theta(\alpha)$; we incorporate both of them and hence we have the above result.


Similarly.

Theorem 2: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1+\alpha)$, on the average, under the assumption of simple uniform hashing.

Now the expected running time is found as $O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ and the authors write it as $O(1)+\frac{\alpha}{2}-\frac{\alpha}{2n}=\Theta(2+\frac{\alpha}{2}-\frac{\alpha}{2n})=\Theta(1+\alpha)$


Again I move on to my hardcore proof, now in $1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ the term $\frac{\alpha}{2n}$ becomes insignificant when $n \rightarrow\infty$ so $1+\frac{\alpha}{2}-\frac{\alpha}{2n} = \Theta(1+\frac{\alpha}{2})$

Now let $a>0$ and $b>0$ be the hidden constants in $O(1)$ and $\Theta(1+\frac{\alpha}{2})$ $\forall n>0$

Now let us consider the function $g'(n)= 1+f'(n)$, where $f'(n)=\alpha$

We choose constants $\lambda ',\mu ' >0$

So for the proof we need to have,

$$\mu' (1+f'(n))< a+b.(1+\frac{f'(n)}{2})< \lambda' (1+f'(n))$$

$$\iff \mu'+ \mu'f'(n))< (a+b)+\frac{b}{2}.f'(n))< \lambda'+\lambda'.f'(n))$$

which holds if $\mu'<\frac{b}{2}<\lambda'$

So from the above proof we have $O(1)+\Theta(1+\frac{\alpha}{2})=\Theta(1+\alpha) \tag 3$,

but I find it quite difficult to find (3) intuitively...


Doubt:

What is the intuition which the authors have used to find the tight bound directly in (3) ?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.