On page 76 of EPI python (The look-and-say problem),
This means the maximum length number has length no more than 2^n. Since there are n iterations and the work in each iteration is proportional to the length of the number computed in the iteration, a simple bound on the time complexity is O(n2^n).
Shouldn’t the time complexity be O(2^n)?
2^0 + 2^1 + … + 2^(n-1) + 2^n = 2^(n+1) - 1
2^(n+1) - 1 << n2^n
By the way, is there a compiled list of errata somewhere?