Explain why time complexity for summing digits in a number of length N is O(logN)
The complexity is proportional to the number of digits. After all, if there are 2,351 digits in the number, the while
loop will iterate 2,351 times.
So the question boils down to, "how many digits are there in N
, asymptotically?". A number with d
digits is between 10^(d-1)
inclusive and 10^d
exclusive. In other words, let d
be the number of digits in N
, and we have the inequalities 10^(d-1) <= N < 10^d
. Taking a logarithm, we have d-1 <= log(N) < d
. (We can maintain the inequalities because logarithms are monotonic.) Adding 1
to the left inequality gives d <= log(N) + 1
, and combining with the previous result, we have log(N) < d <= log(N) + 1
. That is, we've upper-bounded and lower-bounded the number of digits d
by terms that are O(log(N))
.
The above shows that the number of digits is O(log(N))
, or more precisely Theta(log(N))
. The time complexity is the same since it's proportional to the number of digits.
You're confusing two definitions of N
here. Your text cites it as the number itself; your latter description treats N
as the quantity of digits. Yes, the algorithm is O(digits) complexity ... but the quantity of digits is roughly log10(N), where N
is the number.