Al escribir la notación O grande, ¿se pueden usar variables desconocidas? - complejidad de tiempo, big-o

No sé si el idioma que estoy usando en el título es correcto, pero aquí hay un ejemplo que ilustra lo que estoy preguntando.

¿Cuál sería la complejidad del tiempo para este algoritmo no óptimo que elimina pares de caracteres de una cadena?

La función recorrerá una cadena. Cuando encuentra dos caracteres idénticos uno al lado del otro, devolverá una cadena sin el par encontrado. Luego se llama recursivamente hasta que no se encuentra ningún par.

Ejemplo (cada línea es la cadena de retorno de una llamada de función recurrente):

iabccba
iabba
iaa
i

¿Sería justo describir la complejidad del tiempo como O(|Characters| * |Pairs|)? Qué pasa O(|Characters|^2) ¿Se pueden usar pares para describir la complejidad del tiempo aunque el número de pares no se pueda conocer en la llamada de función inicial?

Se me argumentó que este algoritmo era O(n^2)porque no se conoce el número de pares.

Respuestas

Tienes razón en que esto es estrictamente hablando O(|Characters| * |Pairs|)

Sin embargo, en el peor de los casos, el número de pares puede ser igual al número de caracteres (o el mismo orden de magnitud), por ejemplo en la cadena "abcdeedcba" Entonces también tiene sentido describirlo como O(n^2) peor de los casos.

Creo que esto depende en gran medida del problema que pretendes resolver y es la definición. Para algoritmos gráficos, por ejemplo, todos se sienten cómodos con una escritura como complejidad O(|V| + |E|), aunque en el peor de los casos un gráfico denso |E| = |V|^2. En otros problemas, solo miramos el peor caso posible y escribimos O(n^2), sin dividirlo en variables más específicas.

Yo diría que si no hay una convención especial, o no hay datos especiales en el problema con respecto al número de pares, O(...) implica el peor rendimiento y, por lo tanto, O(n^2) sería más apropiado