Notación O

Autor: Javier Eduardo Ojeda Jorge

Recientemente ha salido un libro para los programadores competitivos, llamado Competitive Programmer's Handbook, en tal libro en el capítulo 2 se habla de complejidades y reglas para calcularlas según la Notación O, como está de moda automatizar todo, en esta ocasión se quiere automatizar el cálculo de complejidades y mostrar éstas en notación O.

Las reglas para el cálculo de complejidades en notación O son las siguientes:

• Cualquier instrucción salvo un for tiene complejidad 1
• Un for tiene complejidad n
• Si un for tiene contenido dentro uno o más for, la complejidad es equivalente a n elevado a la cantidad máxima de fors contenidos uno dentro de otro.

Entrada

La primera línea contiene un número entero 1 <= t <= 500 que indica la cantidad de programas a analizar.
Por cada programa, la primera línea tendrá un número entero 1<c<100 que indica la cantidad de líneas de código del programa, en las siguientes c líneas se incluirán las líneas de código sin indentación en lenguaje C++.

Una línea de código puede ser:

Salida

Para cada programa imprimir la complejidad en notación O de las líneas de código, según el siguiente formato O(complejidad), donde complejidad es igual a la complejidad en notación O del programa, vea los ejemplos para mejor entendimiento

Ejemplo de Entrada

4
6
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
}
}
}
8
int x=0;
for(int i=0;i<n;i++){
}
for(int j=0;j<n;j++){
x++;
}
for(int k=0;k<n;k++){
}
6
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
}
}
for(int k=0;k<n;k++){
}
1
int x=0;

Ejemplo de Salida

O(n^3)
O(n^1)
O(n^2)
O(1)