Complejidad Parte 2

[MatiLaB]

Para la parte 2 de la tarea dice que debe tener una complejidad de O(nk) como máximo. Esto es solo para el algoritmo de ordenación, o sea las instrucciones sort-by y double-sort-by, cierto? O el enter y leave deben cumplir con la misma complejidad.
Otra pregunta es sobre si hay una capacidad máxima en la cola o debe depender de la cantidad de pingüinos que se encuentran en ella? Es que estoy en la duda si la idea es manejarlo de manera dinámica o podríamos asumir un numero máximo de espacios (por ejemplo la cantidad de instrucciones que va a tener el test)

[sebacarrascop]

Hola, solo se entrega la dificultad para las operaciones de sort-by y double-sort-by.
Claramente enter y leave deben cumplir con cierta eficiencia para poder pasar los tests en los 5 segundos, fuera de eso no se especifica nada.
No se entrega una capacidad máxima, pero como indicas, lógicamente no pueden haber más enter que eventos.

[MatiLaB]

Ya, muchas gracias. Otra cosa, imprimir los id de los pingüinos ordenados después afectaría a la complejidad o eso ya no entra dentro de la restricción del sort?

[sebacarrascop]

Si debería afectar ya que es parte de lo que te pedimos entregar del evento, sin embargo, imprimir algo de tamaño n es O(n), y dado que la complejidad de ordenarlo es O(nk), luego la complejidad de todo es O(nk + n), lo que sigue siendo equivalente a O(nk).

[GuilleStanke]

Una prreegunta respecto a esto... se pide una complejidad O(nk),, donde k puede ser 100 o 2 (o eso entendí al menos), de esta forma no significa que la complejidad que piden es O(n)? Ya que al k ser una constante que es solamente 100 o 2, podríamos decir que O(100n) = O(2n) = O(n)