4372 is a constant coefficient, not a variable, so it should be dropped from the order of magnitude expression. The network cost of both Napster and Gnutella is dependent on number of searches, not number of users. The fact this is an unchanging number means that order of magnitude expressions are not capable of expressing the difference in efficiency. Order of magnitude expressions are simply the wrong tool for this job. No matter how large the number of Gnutella users becomes, Gnutella will generate no more than about 4,000 times more search messages than Napster.
Comments are welcome.
There are a number of issues that I don't address here. For my purposes scaling means to add users. For some people, scaling means to eliminate the TTL and allow all messages to reach all users. That idea addresses the scalability of broadcasting in general, not the particular use of broadcasting in Gnutella. It is true that Gnutella does involve squaring.