Explain why time complexity for summing digits in a number of length N is O(logN)

Question

Here is the code:

int sumDigits(int n) {
    int sum = 0;

    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }

    return sum;
}

I understand this code, and that the code will take the ones place digit, add that digit to sum, and remove that digit. It keeps doing this until n is equal to 0, at which point it will return sum. Intuitively the runtime will be the number of digits in number N. But I do not understand why this time complexity is O(logN). I thought it was O(N).

Even with explanation like: "A number with d digits can have a value up to 10^d. If n = 10^d, then d = log n. Therefore runtime is O(logN)." does not totally click.

I follow the first part that if d is say 3, then value < 10^d == value < 1000. Meaning max value is 999 with a number of length 3, which I agree with. But after that, when they make the connection that if n = 10^d, I do not understand how 1) they knew to make that equality and 2) how this makes the complexity O(logN) rather than O(N).

Answer 1

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.