Cotas de peor caso

Para cotas de peor caso, la cota inferior es simplemente el logaritmo (base 2) del número total de inputs posibles. Si el conjunto de inputs posibles es $U$, entonces no es posible representar a todos sus elementos usando siempre menos de $\log_2 |U|$ bits. La razón es que el número total de descripciones que usan menos de $\log_2 |U|$ bits es $\sum_{\ell=0}^{\log_2|U|-1} 2^\ell = |U|-1$, es decir, no hay suficientes descripciones distintas para todos los elementos de $U$. Por lo tanto, cualquier algoritmo a través de cuyas comparaciones se pueda identificar el input requiere $\log_2 |U|$ comparaciones en el peor caso. Note que, para hablar de bits, las comparaciones deben ser binarias, es decir, con dos resultados posibles (por ejemplo, $\le$ y $>$).

Volvamos al juego de las 20 preguntas. Si $A$ conoce a más de $2^{20}$ personajes distintos, entonces $B$ no tiene suficientes preguntas para poder ganar siempre, pues no bastan 20 "bits" sí/no para identificar a todos los posibles personajes. Dicho de otro modo, para cualquier estrategia que $B$ tenga, siempre existe un subconjunto de al menos dos personajes que no se llegan a distinguir con las primeras 20 preguntas.

Por otro lado, si $A$ conoce no más de $2^{20}$ personajes, entonces $B$ puede ganar siempre si busca preguntas balanceadas, es decir que a cada paso dividan el conjunto de personajes posibles a la mitad. Es por eso que preguntas como "¿tiene pelo negro?" o "¿nació en este continente?" son mejores que "¿se trata de Napoleón?" como primeras preguntas.