7
$\begingroup$

I was attending a class on analysis of hash tables implemented using chaining, and the professor said that:

In a hash table in which collisions are resolved by chaining, an search (successful or unsuccessful) takes average-case time θ(1 + α), under the assumption of simple uniform hashing.

and

The worst-case time for searching is θ(n) plus the time to compute the hash function.

These are quoted from out textbook, ITA. Here α is the load factor, which is equal to n/m where n is the total number of elements to be inserted to the hash table and m is the size of the hash table (which is a constant for each implementation).

My confusion arises from the thinking that

θ(1 + α) = θ(α) = θ(n/m) = θ(n)

So I claimed that θ(1 + α) = θ(n), ie the average case and worst case time complexities are the same and the professor disagrees with me.

She asked me to find out by myself why I am wrong. I did some brainstorming and the only deduction I can make is that either I am wrong in assuming that m is a constant or asymptotic notations can't be used to compare between worst-case and average-case running time in this case. Please help me find what is wrong here. Also I don't understand why θ(1 + α) is not written simply as θ(α) and also why the professor insists on the value of α being less than, equal to, or greater than 1

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The reason that we are using $\Theta(1+\alpha)$ rather than $\Theta(\alpha)$ is that $\alpha$ could be very small. Imagine for example that the hidden constant in both $\Theta$s is one, and that $\alpha=0.000001$. There is a large difference between $1.000001$ and $0.000001$.

Regarding your wrong deduction, note that the first paragraph mentions average case and the second worst case. It's true that the average case is at most the worst case, but not the other way around.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So am I wrong is saying that the time complexities of both average case and worst case are both θ(n)? $\endgroup$
    – daltonfury42
    Commented Mar 2, 2016 at 8:56
  • $\begingroup$ Yes, that's incorrect in general. Your professor was right when she suggested you find out yourself why. I tried to give you a hint in my answer. $\endgroup$
    – Yuval Filmus
    Commented Mar 2, 2016 at 8:57
  • $\begingroup$ Here n is the input size and m is a constant. If generally θ(kn) = θ(n) where k is a constant, then why is θ(1/m * n) ≠ θ(n) where 1/m is a constant. $\endgroup$
    – daltonfury42
    Commented Mar 2, 2016 at 9:04
  • $\begingroup$ We don't think of $m$ as constant, since it's not really constant. Different instances of the data structure can have widely different $m$. It's as if you would say that the space is $O(1)$ rather than $\Theta(m)$. $\endgroup$
    – Yuval Filmus
    Commented Mar 2, 2016 at 9:42
  • 1
    $\begingroup$ Whenever you run an algorithm on a particular input, all the parameters are fixed. That doesn't mean that when we compute the asymptotic performance of an algorithm we assume that they are constant. In other words, $m$ and $n$ are both values of the same "type". You can call them parameters, but that's not a particularly good term. $\endgroup$
    – Yuval Filmus
    Commented Mar 2, 2016 at 12:02
0
$\begingroup$

O(1+α) is only equal to O(α) when α becomes much greater than 1 and for hash tables that is usually not the case. For a chaining hash table it would typically be around 1 and for an open addressing hash table it would be less than or equal to 1. If α much greater than 1 we would be calling it a hash table any more but rather a bunch of lists that indeed will have an asymptotic complexity of O(n).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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