Articles Weblogs Books School Short Cuts Podcasts  
P2P Memebag

O(N2) efficiency

Order of magnitude expressions show the growth rate of a function as the value of some input increases. In the context of peer to peer, O(some expression involving N) is usually used to describe the efficiency of some network design, where N is the number of nodes and the function is the amount of work needed to support that number of nodes.

N2 (often typed out longhand as "O(N^2)") is quite a lot larger than N if N is large, so O(N2 ) means that the amount of work to support each new node increases as the total number of nodes gets larger. Ln(N) (the natural logarithm of N) is smaller than N itself, so O(ln(n)) means that the amount of work to support each new node decreases as the total number of nodes gets larger. N is, as you would expect, N, so O(N) means that the amount of work required to support each new node stays constant as the total number of nodes gets larger.

O(N2 ) means that ineffiency grows faster than utility. O(ln(N)) means that inefficiency shrinks as usage grows (there are increasing returns), and O(N) means that inefficiency doesn't change with volume. A system where inefficiency increases with volume eventually chokes available resources to death. More adoption of such a system makes it less useful.

If P2P really does have to be O(n2 ), then it is likely to be a dead end. So the conversation about efficiency is really a conversation about whether P2P can survive success.

See here for details on the math of order of magnitude expressions, here for Jordan Ritter's look at the math, and here for a more partisan take on the issue (by the author of this glossary entry).

Back to Index