I\'ve been using the Stanford Algorithms (1) Coursera course, and in a descripti

Question

I've been using the Stanford Algorithms (1) Coursera course, and in a description of a problem, the lecturer said that in the problem of allocating n processes to n servers at random, the sample space of allocations is n^n, and each has equal probability.

Intuitively this seems unlikely to me: if you imagine each server having a number and that number being the number of processes assigned, you wouldn't have the case of two servers being assigned n processes; yet the n^n -- as far as I can see -- assumes that such allocations are possible.

Am I missing something?

Explanation / Answer

The number nn can be easily obtained if you think the problem in the other direction: each process has n choices and therefore n processes has nn possible choices in total. Of course it is impossible that two servers have n processes. If a process can be assigned to more than one server, the number of possible assignments is far more than nn.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.