Why do people say that bitcoin scales according to O(n^2)?
n is the number of users. It is assumed that the number of transactions is Ө(n), and that the number of full nodes who must know all transactions is also Ө(n), so the total information (that needs to be propagated, verified and stored) is n*Ө(n) = Ө(n^2).

The assumption about the nodes requires clarification according to context, because there is no actual need for the number of nodes to scale with n.

k is the proportionality constant implicit in the Big Theta notation.