Descubrí algo nuevo (TIL): Los bucles anidados for/while pueden tener una complejidad temporal de O(N) en algunos casos (DSA para entrevistas técnicas)

La complejidad temporal de un bucle anidado en Python depende de cómo se estructuran los bucles. Un bucle while dentro de un bucle for aún puede resultar en una complejidad O(N) en ciertos casos. En el primer ejemplo, el bucle while se ejecuta solo una vez por iteración del bucle for y hace trabajo constante, lo que resulta en una complejidad O(N). En el segundo ejemplo, el bucle while se ejecuta un número constante de veces por cada iteración del bucle for, lo que nuevamente resulta en una complejidad O(N). En el tercer ejemplo, la condición del bucle while significa que solo incrementará una variable hasta N en total, lo que resulta en una complejidad O(N). La lección clave es que si el número de iteraciones del bucle while interno es independiente del bucle for, la complejidad combinada puede seguir siendo O(N). La complejidad solo sería O(N^2) si el bucle while se ejecutara N veces por cada iteración del bucle for. Un ejemplo de complejidad O(N^2) es cuando el bucle while se ejecuta N veces por cada iteración del bucle for. En este caso, el bucle for se ejecuta N veces y el bucle while se ejecuta N veces por cada iteración del bucle for, lo que resulta en una complejidad O(N^2). La estructura de los bucles anidados determina la complejidad temporal general.