Factorial digits sum puzzle, time complexity survey

Question

What would you say the time-complexity of the foo function is (relative to n)?

DIGIT_FACTORIAL = [1]
for x in range(1, 10):
    DIGIT_FACTORIAL.append(DIGIT_FACTORIAL[x-1]*x)

def digit_factorial(x):
    return DIGIT_FACTORIAL[x]

def foo(number_of_digits):
    n = 10**number_of_digits
    i = n//9

    while i != sum(digit_factorial(int(x)) for x in str(i)) and i < n:
        i += 1

    if i < n:
        return i
    return None 

Answer 1

O(n log(n))

Explanation:

Every while loop runs from 111...1 == n/9 to n. This means that the while loop runs n*8/9 times. O(n * some_constant) == O(n).

Inside each iteration, the sum is over all the digits in i. There are log10(n) - 1 digits in i. O(log10(n) - 1) == O(log(n)).

Nesting the two makes O(n log(n)).

Note that the above explanation does not take into account that the loop could break early if i == sum(...). That is because the upper bound for sum(digit_factorial(int(x)) for x in str(i)) is 9! * number_of_digits which is always less than i when number_of_digits is greater than 7 or so.