This doesn't sound remotely right. If n is the number of elements, k is the number of distinct elements, and its O(n + k) as the author describes, k is trivial

This doesn't sound remotely right. If n is the number of elements, k is the number of distinct elements, and its O(n + k) as the author describes, k is trivially bounded by n (you can't have more distinct elements than you do elements). Resulting in O(n) complexity, how did you get O(n^2)?