# Gavin Andresen
# 2013-02-18 18:29:47
# https://bitcointalk.org/index.php?topic=144895.msg1537235#msg1537235

Half-baked thoughts on the O(N) problem: @p{par}

So, we've got O(T) transactions that have to get verified. @p{par}

And, right now, we've got O(P) full nodes on the network that verify every single transaction. @p{par}

So, we get N verifications, where N = T*P. @p{par}

The observation is that if both T and P increase at the same rate, that formula is O(N^2). @p{par}

... and at this point your (and gmaxwell's) imagination seems to run out, and you throw up your hands and say "We Must Limit Either T or P." @p{par}

Really? @p{par}

If we have 20,000 full nodes on the network, do we really need every transaction to be verified 20,000 separate times? @p{par}

I think as T and P increase it'd be OK if full nodes with limited CPU power or bandwidth decide to only fetch and validate a random subset of transactions. @p{brk}