oreilly.comSafari Books Online.Conferences.
Articles Radar Books  

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

P2P Weblogs

Richard Koman Richard Koman's Weblog
Supreme Court Decides Unanimously Against Grokster
Updating as we go. Supremes have ruled 9-0 in favor of the studios in MGM v Grokster. But does the decision have wider import? Is it a death knell for tech? It's starting to look like the answer is no. (Jun 27, 2005)

> More from O'Reilly Developer Weblogs

More Weblogs
FolderShare remote computer search: better privacy than Google Desktop? [Sid Steward]

Data Condoms: Solutions for Private, Remote Search Indexes [Sid Steward]

Behold! Google the darknet/p2p search engine! [Sid Steward]

Open Source & The Fallacy Of Composition [Spencer Critchley]