Understanding Example 16 printing the powers of 2 from Big O notation - Cracking the Coding Interview

Question

Had the author missed to compute I/O calls?

The following function prints the powers of 2 from 1 through n (inclusive). For example, if n is 4, it would print 1,2, and 4. What is its runtime?

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;
  }
}

the runtime is O(log n)

According to the Example 12 (string permutations) the length of argument of System.out.println() call makes sense:

Executing line 7 takes O(n) time since each character needs to be printed

From I/O perspective we need to print powers of 2 from 0 to K, where K is [log(N)], the amount of characters to print for 2^X is [1 + X/log(10)], so the total amount of characters to print is [K + 1 + K*(K+1)/2log(10)] and the runtime is O(log²N) but not O(log N)

PS.

The Example 15 - printing memoized Fibonacci numbers seems to have the same drawback:

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];
}

We're doing a constant amount of work N times, so this is O(n) time.

The amount of characters to print for the sequence of first N Fibonacci numbers ~ N², so the runtime should be O(N²).

Answer 1

You are correct. The total amount of characters being printed out is Θ(log² n), and so the total amount of work done by the code works out to Θ(log² n) rather than O(log n), assuming we count the cost of printing each character. It's somewhat common when doing back-of-the-envelope big-O calculations to leave out the cost of printing out the result, though in Theoryland you have to factor in those costs.

That being said, one could make a reasonable argument that any int value takes up a fixed amount of characters when printed out on a computer (on a 32-bit machine printing a 32-bit integer requires at most 11 characters, on a 64-bit machine printing a 64-bit integer requires at most 21 characters, etc.). You could therefore argue that the cost of printing any integer is O(1) for any fixed machine, even though in reality there's some auxiliary parameter w representing the size of a machine word and the cost of printing a w-bit integer is O(w).

For an introductory exercise in learning to reason about big-O, I think it's pedagogically fine to gloss over this detail. But if I were teaching a more advanced theory course, we'd definitely need to factor in these costs.