He leído que la operación de inserción en un conjunto solo lleva tiempo de registro (n). ¿Cómo es eso posible?

Para insertar, primero hemos encontrado la ubicación en la matriz ordenada donde debe ubicarse el nuevo elemento. Usando la búsqueda binaria toma log (n). Luego, para insertarlo en esa ubicación, todos los elementos que lo sucedan deben desplazarse un lugar a la derecha. Tarda otro n tiempo.

Mi duda se basa en mi entendimiento de que el conjunto se implementa como una matriz y los elementos se almacenan en orden ordenado. Por favor corrígeme si mi entendimiento es incorrecto.