The article explicitly states that sorting is O(n log n), giving rise to log n per element. I think you missed that I'm talking about adding/removing/reading a single element at a time.