Pode dar um exemplo de uma avaliação de complexidade de algoritmo que se revelou incorreta ou insuficiente?

O erro na avaliação da complexidade do algoritmo está frequentemente relacionado com suposições simplificadas sobre o comportamento dos dados ou com a ignorância dos piores casos.

Por exemplo, ao usar ordenação por inserção, muitas vezes dizem que o algoritmo funciona em O(n) se os dados estiverem quase ordenados. No entanto, se os dados forem aleatórios ou estiverem em ordem inversa, a complexidade torna-se O(n²). Ignorar esses casos pode levar a uma avaliação insuficiente.

No desenvolvimento iOS, pode-se citar um exemplo usando UITableView e o método dequeueReusableCell. Se assumirmos que a reutilização de células é sempre eficiente e não considerarmos casos em que muitas células novas são criadas (por exemplo, ao fazer scroll rápido com diferentes tipos de células), podemos subestimar os custos de memória e tempo.

Portanto, é importante considerar todos os cenários e características dos dados ao avaliar a complexidade e o desempenho.