[bmm6o]

Parent is talking big-O and so is ignoring that it isn't exactly k^2. Depending on how you count (do 2 nodes require 2 connections or 1 bi-directional connection) it's k(k-1).