N choose two, not N^2. The latter double counts and also counts people communicating with themselves. For example, with 2 people, it is not 4 paths of communication, but just 1.

N choose two is n*(n-1)/2, which yields the right answer

In asymptotic analysis, they are the same. Except, that analysis does not make sense, asymptotic refers to the growth of the function as values approach effectively infinite