CODEWITHSUNDEEP
pythontime-complexity
Praful Bagai
Praful Bagai

Reputation: 17372

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

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)?

Upvotes: 2

Views: 434

Answers (3)

DAle
DAle

Reputation: 9117

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.

Upvotes: 1

perigon
perigon

Reputation: 2095

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.

Upvotes: 0

Mureinik
Mureinik

Reputation: 311073

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).

Upvotes: 5

Related Questions