Comprensión del ejemplo 16 de la impresión de las potencias de 2 desde la notación Big O – Descifrando la entrevista de programación.

¿Habría omitido el autor el cálculo de las llamadas de E/S?

La siguiente función imprime las potencias de 2 desde 1 hasta n (inclusive). Por ejemplo, si n es 4, imprimiría 1, 2 y 4. ¿Cuál es su tiempo de ejecución?

int powersOf2(int n) {
  if (n < 1) {
    return 0;
  } else if (n == 1) {
    System.out.println(1);
    return 1; 
  } else {
    int prev = powersOf2(n / 2); 
    int curr =prev * 2; 
    System.out.println(curr); 
    return curr;
  }
}

El tiempo de ejecución es O(log n)

Según el ejemplo 12 (permutaciones de cadena), la longitud del argumento de la llamada System.out.println() tiene sentido:

Ejecutar la línea 7 toma tiempo O(n) ya que cada carácter debe imprimirse.

Desde la perspectiva de E/S, necesitamos imprimir las potencias de 2 desde 0 hasta K, donde K es [log(N)], la cantidad de caracteres a imprimir para 2^X es [1 + X/log(10)], por lo que la cantidad total de caracteres a imprimir es [K + 1 + K*(K+1)/2log(10)] y el tiempo de ejecución es O(log²N) pero no O(log N)

PD.

El ejemplo 15 – imprimiendo números de Fibonacci memorizados parece tener la misma limitación:

void allFib(int n) {
  int[] memo = new int[n + 1]; 
  for (int i = 0; i < n; i++) {
    System.out.println(i + ": " + fib(i, memo));
  }
}

int fib(int n, int[] memo) {
  if (n <= 0) return 0;
  else if (n == 1) return 1;
  else if (memo[n] > 0) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

Estamos haciendo una cantidad constante de trabajo N veces, por lo que esto es tiempo O(n).

La cantidad de caracteres a imprimir para la secuencia de los primeros N números de Fibonacci ~ N², por lo que el tiempo de ejecución debería ser O(N²).