>OK. O() notation normally refers to computational complexity, but ... I still don't get it - the vast >majority of users don't run relaying nodes that take part in gossiping. They run web or SPV >wallets. And the nodes that do take part don't connect to every other node.

It's a little scary, IMO, that the fact that the majority of nodes don't relay and only perform the most rudimtentary level of validation if any is considered an acceptable feature of the protocol.

- Eric Lombrozo