1
$\begingroup$

I was reading CLRS and in theorem 11.1 it states:

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

I was trying to understand how to express this theorem with quantifiers ($\exists, \forall$) and how it relates to "average-case" time (precisely, what they mean with average case time).

Is the theorem a statement that holds for all or any key? Or does it hold for all key on average and what does "on average" mean rigorously?

Usually, I like separating the terms expectation and average because the have different meanings. Expectation usually I think of it as the expected value of something according to some underlying distribution. For Average I think of the average value given a sample. So with these in mind, is the "average-case" scenario the same as the average running time for any key? i.e. Let $T_k$ denote the amount of time to search of a key $k$. This is a random quantity because it depends on the key we search for. Define the average-case runtime for any search to be $Search = \sum^n_{k=1} T_k$. Is the theorem statement in CLRS statement about the random variable $Search$ I just defined? (Which takes into account all keys at once and hence, applied for "any key" I guess). Or what do they mean by average-case precisely?

$\endgroup$
  • 1
    $\begingroup$ Are you asking what "average-case time" means? If so, what research have you done? This is a standard concept in algorithms. What textbooks have you checked? $\endgroup$ – D.W. Feb 16 '16 at 5:14
  • 1
    $\begingroup$ its not standard, algorithms are usually analyzed in worst-case. Thats standard. Average case can be when the algorithms have an input distribution, or even in amortized analysis is a different framework for "average case". Some people even confuse average with expectations. What I am saying is that I can't follow what CLRS says cuz they don't rigorously define what they mean by average case in exactly that chapter of CLRS page 258 chapter 11 nor do they have clear quantifiers for when their statements hold for searches. Maybe I'm dum cuz I can't tell when its not clearly stated. $\endgroup$ – Charlie Parker Feb 16 '16 at 5:58
  • 1
    $\begingroup$ Average-case analysis is totally standard: you just need to read the right textbooks. I suggest you read a textbook on randomized algorithms, or a textbook that covers them. For instance, Randomized Algorithms by Motwani and Raghavan is good, though might be a bit more advanced than what you're looking for. Amortized analysis is different; average-case running time is about averaging over the internal random bits that the algorithm uses. $\endgroup$ – D.W. Feb 16 '16 at 6:08
  • 1
    $\begingroup$ That maybe be the case for that book, but CLRS is the most standard book for algorithms and worst case analysis is obviously the most prominent one. Since those text books are more familiar for very specialized courses like randomized algorithms close, its no wonder I've not read them (though I've seen them advertised for those classes). Regardless, thats getting tangential. The point is I am not familiar with those books and CLRS didn't explicitly define in that chapter what they mean, hence, my confusion. But I do have good background in probability, so that isn't my problem. $\endgroup$ – Charlie Parker Feb 16 '16 at 6:12
  • 1
    $\begingroup$ You should do a significant amount of research before asking, and exhaust all reasonable resources. I haven't checked whether CLRS has any coverage of this, but if CLRS doesn't have the answer, don't just give up. There are lots of things CLRS won't have the answer to -- it's worth developing the ability to find other relevant resources! $\endgroup$ – D.W. Feb 16 '16 at 6:15
2
$\begingroup$

The average-case running time (or expected running time) of a randomized algorithm is typically defined to be the expectation of the running time of the algorithm, with respect to the random coins used by the algorithm (i.e., the random bits used internally in the algorithm).

If this number depends on the input, we often choose the worst case over all inputs. If it matters, a good source should say what it means.

Note that this has nothing to do with amortized analysis. Amortized running time is something completely different; it is about the running time of a sequence of operation, and applies equally well to deterministic algorithms, whereas average-case running time applies only to randomized algorithms.


Therefore, the statement you are quoting means: for all keys, the running time to search for a particular key is a random variable whose expectation is $\Theta(1+\alpha)$. (It's a random variable, because the running time depends on the randomness in the hash function.)


Caveat: You may occasionally find some situations where a particular distribution on the inputs is specified, and one takes the expectation of the running time with respect to the random choice of input. However, this usage is rare and it would probably be poor form to use average-case for this meaning, if it's not clear from context that this is what was intended.

$\endgroup$
  • $\begingroup$ That is not how CLRS defines average-case running time.In fact they make the clear distinction btw the two in page 115 at the bottom & then in page 117 (defining the two). Average-case & expected runtime are different in CLRS. Maybe this is a confusing non-standard thing across different books.Regardless,unfortunately,I already knew your distinction and doesn't clarify the theorems 11.1/11.2 which Im trying to understand.I will try to think how to re-phrase my question to make it more clear.Apologies for that, let my try again to make it clear what I'm confused about. Though thnx for the help. $\endgroup$ – Charlie Parker Feb 16 '16 at 6:20
2
$\begingroup$

There are two prominent uses of the term "average" in algorithm analysis.

  1. Average-case as a special case of expected costs

    Here, "average case" just means "expected case w.r.t. uniform distribution". Since we usually analyse with uniform inputs in mind (everything else is hard, and there's not much reason to prefer one distribution over the other in most cases).

    Example: the average-case running-time cost of sorting algorithms is often analyzed w.r.t uniformly-random permutations.

  2. Average cost in the classic sense.

    When analyzing data structures, we can look at average costs across the contained elements for a fixed instance -- no probability distribution here (well, you could...). That is, we may still have/want to consider a worst-, average- or best-case instance.

    Example: Consider BSTs. The average search cost of a given tree is the total cost for searching all contained elements (one after the other) divided by the number of contained elements. This is a classic quantity in AofA called internal path length.

Note: There are situations where average and expected do not usually mean the same thing. For instance, the expected (also: average-case) height of BSTs is in $O(\log n)$ but the average height is in $\Theta(\sqrt{n})$. That is because "expected" is implicitly (by tradition) meant w.r.t. uniformly-random permutations of insertion operations whereas "average" means the average over all BSTs of a given size. The two distributions are not the same, and apparently significantly so!

Recommendation: Whenever you use "expected" or "average-case", be very clear about which quantities are random w.r.t. which distribution.


The specific sentence you quote is indeed not clear if read in isolation -- if you ignore that CLRS specify exactly what "simple uniform hashing" means on the very same page.

There are two potentially random variables here: 1) the content of the hashtable itself, and 2) the key searched for. Simple uniform hashing is a simple way of specifying both.

  1. We abstract from sequences of insertions¹ and just assume that every one of the $n$ elements we inserted independently hashed to each of the $m$ addresses with probability $1/m$.
  2. We assume that the searched key hashes to each address with probabilty $1/m$.

That's how the proof works: our search hits each list with probability $1/m$ (cf 2), and they all have the same expected length of $n/m$ (via 1). Hence, the expected cost (under this specific model) for searching for $x$ not in the table is proportional to

$\qquad\displaystyle\begin{align*} T_u(x,n,m) &= 1 + \sum_{i=1}^m \operatorname{Pr}[h(x) = i] \cdot \mathbb{E}[\operatorname{length}(T[i])] \\ &\overset{1,2}{=} 1 +\sum_{i=1}^m \frac{1}{m} \cdot \frac{n}{m} \\ &= 1 + \frac{n}{m}. \end{align*}$

The "$+1$" is there to account for computing $h(x)$ and accessing $T[h(x)]$, the sum represents the cost for searching along the list.


  1. That is fair since the sequence of insertions does not have as much impact on the resulting structure as for, say, BSTs. The hash function shakes everything up. We don't want to talk about the precise interaction of sequence and hash function, so we just assume that the result of both is independently uniform -- that's something we can work with. It may not represent reality, of course!
$\endgroup$
  • $\begingroup$ There are two sources of randomness, the keys and the lengths of the table. The lengths of the chains is clearly dependent on how the hash function spreads elements out randomly. However, the part that isn't 100% clear from your answer is how you took care of the distribution of which keys we searched for. If $$E[T] = \sum^{n}_{i=1} E_{t \sim Pr[T]} [T_{h(k)}] Pr[Key = k]$$ is the expected time to search for any key, then, why can't you just simply conclude $E_{t \sim Pr[T]} [T_{h(k)}] \leq E_{n \sim Pr[N]} [n_{h(k)}] = \frac{n}{m}$ and just call everything done by pluging it in to $E[T] $? $\endgroup$ – Charlie Parker Feb 26 '16 at 22:47
  • $\begingroup$ See the two numbered list items. The simple uniform hashing assumption allows us to ignore the actual keys. $\endgroup$ – Raphael Feb 27 '16 at 14:59
  • $\begingroup$ sorry if this is super easy/obvious to you. But how does that assumption make this possible? If you could write some details for this I would be really grateful. $\endgroup$ – Charlie Parker Feb 29 '16 at 0:43

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.