The calculation that leads to (N2-N)/2 is based on the fact that each node connects to N-1 other nodes (if there are N nodes.) Each node has this many wires coming out of it, so there are at least N(N-1) wires. However, a wire from A to B connects it the same as a wire from B to A, so only half of these wires are not redundant, leading to N(N-1)/2, which is (N2-N)/2. Theorists say that this function is approximately N2 because as N gets very large, the -N amount becomes insignificantly small. However, dividing N2 by 2 seems to drastically change the function, but for various theoretical reasons multiplication of a function by a constant doesn't change the function's broad behavior. Fig. 23.11.2 shows the arrangement of wires leading to (N2-N)/2.
|