What is the time complexity of looping over the array and then splitting the number into digits?

Question

If we had a case where we are looping over the array of numbers and the numbers can scale to infinity, and inside of each iteration we are looping over digits of each number, so for number 125556 we would loop through six numbers, 1, 2, 5, 5, 5, and 6, is the time complexity of this algorithm just O(N), where N represents the numbers in the array, or it is O(N*K) where K is the number of digits in the number. In this case K is always less than N, so I am unclear whether this is multiplication or we can just disregard the number of digits?

Answer 1

The algorithm you describe is always O(N * K).

However, if you know something about the relationship between N and K, then you can simplify the expression. For instance, if the numbers are guaranteed to fit in a 32-bit integer representation on a computer, then K is a constant and your algorithm is O(N). If K < N, then you can say O(N²).

But if you have no assumption on K, then you have to go with O(N * K), as K could be significantly larger than N or vice versa. Intuitively, your time complexity depends on two factors, so you need to express it with two variables unless they depend on each other.

Edit:

Since you clarified that you are looping through the numbers in order, as in 1, 2, ..., N, we now have some information on the relationship between K and N. In fact, K = O(logN), so the algorithm can be expressed as O(N logN).

If you are confused about how we know that K = O(logN), then take any power of 10 as an example. You will find that 10^K has log₁₀ 10^K + 1 = K + 1 digits. Similarly, any number X has O(log X) decimal digits (notice that the base of the logarithm does not matter in the big-O notation).