En el libro Programando entrevistas expuestas dice que la complejidad del programa a continuación es O (N), pero no entiendo cómo esto es posible. ¿Alguien puede explicar por qué es esto?¿Cuál es la complejidad de este código cuyo ciclo anidado repetidamente dobla su contador?
int var = 2;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j *= 2) {
var += var;
}
}
* "Se dice" * ¿Qué dice? Cuéntanos qué es lo que estás asumiendo aquí. – dmckee
Hice la edición, disculpe la vaguedad –
Esta estructura de bucle está muy relacionada con la del algoritmo de heapify y el análisis será muy similar. – templatetypedef