Adam claims that the network overhead in scaling Bitcoin is O(n^2), where n=transactions
Mike counters that it is O(nm), where m=nodes
The latter makes more sense to me, and further, that m is not as significant as it appears because it is highly parallelized.
The way I see it, if
m nodes need to be made aware of
n transactions, then the network overhead for bandwidth is O(
nm).
If we assume that the number of nodes is linearly proportional to the number of transactions, then
m =
kn and the network overhead is O(
n2). But as you mentioned,
m is probably not this significant. In fact, for the last several years
m has gone down as
n has gone up, so the network overhead
empirically is more like O(
n0.7) (i.e., better than linear).
Interesting question: right now the Bitcoin network processes about 1 transaction per second while the Visa network processes about 2000. Right now there are about 6,000 full nodes. If Bitcoin grew to reach Visa's level of transactions per second (2000X growth), would we expect the number of full nodes to grow from 6,000 to 12,000,000?
The other thing I don't understand is why people focus on the
network overhead rather than the overhead to run a single node. As far as I can see, this should always be roughly O(
n).