Calculating the time complexity of a python function

Question

Hey I am a private tutor in Python for students in the "Intro to CS" class in a nearby university. My student gave me a question from a test about calculating the time complexity (Big O Notation) of some function, and I am having a hard time myself coming up with a good answer and explanation to how I got it. This is the function:

def oh(lst, n):
    if n==1:
        print(lst)
        return
    for i in range(n):
        oh(lst, n-1)
        if n%2==0:
            lst[i], lst[n-1] = lst[n-1], lst[i]
        else:
            lst[0], lst[n-1] = lst[n-1], lst[0]

Now the way I see it, it's supposed to be something along the lines of n**(n-1) or something big like that, since every recursive call makes n calls to the next recursion, I tested the function with a wrapper to see how it runs for n=10 and some lst with 10 ints, and count the operations manually and got something that vaguely fits my assumption (about 15 million operations), but it's not precise enough..

Your estimate looks good to me. I'm not sure what's the purpose of this function, but it has the worst time complexity I've seen so far. — Sergio Tulentsev
– Sergio Tulentsev, Commented Jan 11, 2022 at 12:33
it appears to be some sort of attempt at a bubble sort, which is O(n^2) which is what this looks like — gold_cy
– gold_cy, Commented Jan 11, 2022 at 12:37
Upon closer inspection, the complexity appears to be O(n!). With a list of 5 elements, we will do 5 passes of oh(lst, 4), each of which will do 4 passes of oh(lst, 3) and so on. — Sergio Tulentsev
– Sergio Tulentsev, Commented Jan 11, 2022 at 13:01
agree with sergio on this one. the recursive call is inside a loop of range(n), where n decreases by 1 with each recursive call. looks to be O(n!) — Mulan
– Mulan, Commented Jan 11, 2022 at 15:15

Krishna murthy · Accepted Answer · 2022-01-23 16:19:40Z

1

T(n) = n*T(n-1) + n

Where T(n) is time taken for input list of size n

This gives O(n!) time complexity. If you expand the relation above, you will get a more precise answer, but the complexity will be O(n!)

answered Jan 23, 2022 at 16:19

Krishna murthy

1912 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Calculating the time complexity of a python function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related