Buenas tardes,
Este ejercicio dice:
Exercise 3.10.74 - Show how to elect a leader in a complete network with O(nlogn) messages in the worst case but only O(n) on the average
En el libro describe 2 algoritmos, el cual el primero (territory acquisition) lo resuelve con O(nlogn) mensajes, y en el segundo utiliza la enumeración de los puertos para ir reduciendo la cantidad de aristas del anillo aprovechando la comunicación directa entre los nodos para lograr resolver el problema con O(n) mensajes.
Supongo que se espera una respuesta relacionada con el primero de los algoritmos, pero el O(n) para el promedio no me queda claro, cual sería el promedio de los casos.
Alguna ayuda con el ejercicio?
Muchas gracias