Eu li que a operação de inserção em um conjunto leva apenas log (n) tempo. Como isso é possível?

Para inserir, primeiro encontramos o local na matriz ordenada onde o novo elemento deve ficar. Usando a pesquisa binária, é necessário log (n). Em seguida, para inserir nesse local, todos os elementos sucessivos devem ser deslocados para a direita. Leva outro n tempo.

Minha dúvida é baseada em meu entendimento que o conjunto é implementado como uma matriz e os elementos são armazenados em ordem de classificação. Por favor, corrija-me se meu entendimento estiver errado.