What's the time complexity for the following python function?

Question

def func(n):
    if n == 1:
        return 1
    return func(n-1) + n*(n-1)

print func(5)

Getting confused. Not sure what exactly it is. Is it O(n)?

Answer 1

Calculating the n*(n-1) is a fixed time operation. The interesting part of the function is calling func(n-1) until n is 1. The function will make n such calls, so it's complexity is O(n).

Answer 2

If we assume that arithmetic operations are constant time operations (and they really are when numbers are relatively small) then time complexity is O(n):

T(n) = T(n-1) + C = T(n-2) + C + C = ... = n * C = O(n)

But the multiplication complexity in practice depends on the underlying type (and we are talking about Python where the type depends on the value). It depends on the N as N approaches infinity. Thus, strictly speaking, the complexity is equal to:

T(n) = O(n * multComplexity(n))

And this multComplexity(n) depends on a specific algorithm that is used for multiplication of huge numbers.

Answer 3

As described in other answers, the answer is close to O(n) for practical purposes. For a more precise analysis, if you don't want to make the approximation that multiplication is constant-time:

Calculating n*(n-1) takes O(log n * log n) (or O(log n)^1.58, depending on the algorithm Python uses, which depends on the size of the integer). See here - note that we need to take the log because the complexity is relative to the number of digits.

Adding the two terms takes O(log n), so we can ignore that.

The multiplication gets done O(n) times, so the total is O(n * log n * log n). (It might be possible to get this bound tighter, but it's certainly larger than O(n) - see the WolframAlpha plot).

In practice, the log terms won't really matter unless n gets very large.