Transferencia

Fuera de la computadora

Buscar un nombre en una guía telefónica ordenada, abriéndola por la mitad cada vez, es O(log n). Buscar el número de teléfono de alguien sin saber su nombre, en la misma guía, es O(n): el orden por nombre no ayuda a buscar por número.

Una agenda de n contactos se guarda ordenada por apellido. ¿Qué costo tienen buscar por apellido y buscar por teléfono?Por apellido O(1); por teléfono O(n), porque el orden permite ir directo al apellidoPor apellido O(log n); por teléfono O(n): el orden solo ayuda a la clave por la que se ordenóPor apellido O(log n); por teléfono O(log n), porque ordenada cualquier búsqueda descarta la mitadLas dos O(n): el orden solo sirve si la agenda no cambia entre búsquedas