I wrote a program to calculate the factorial of a number, and store the digits of the result in a Python list.

1. To find the factorial, I run a loop that takes O(N) and store the result in "ans"
2. To find the number of digits of "ans", I run another loop that takes log10(ans).
3. Finally, I just reverse the list in-place

I am struggling to see what the total Time Complexity (TC) is. I believe:

TC = O(d) = O(log10(ans)), since d > N for N->inf, where d (number of digits in ans) = log10(ans), and ans ∈ O(N).

Am I wrong? Is there any other way to express the total TC, maybe something like a nested Big-O:

O(log10(O(N))) ???

Note: log10 means logarithm with base 10

Below is my code:

def factorial(N):
        ans = N
        ans_digits = []

        # 1. O(N)
        while N > 1:
            N -= 1
            ans *= N

        # 2. O(log10(ans))
        while ans > 0:
            digit = ans % 10
            ans //= 10
            ans_digits.append(digit)

        # 3. O(log10(ans))
        for i in range(len(ans_digits)//2):
            temp = ans_digits[i]
            ans_digits[i] = ans_digits[-(i 1)]
            ans_digits[-(i 1)] = temp

        # Shorter way of doing 2 and 3: O(log10(ans))
        #ans_digits = str(ans).split()

        return ans_digits

CodePudding user response：

Thanks to @user3386109, by Stirling's approximation to factorials, the Time Complexity can be expressed in terms of N as:

TC = O(d) = O(logN!) = O(NlogN - c.N   O(logN)) = O(NlogN)

where log has base 10 and N is an integer.