what is the time complexity of this recursive function in python?

Question

I have this function:

def rec(lst):
    n = len(lst)
    if n <= 1:
        return 1
    return rec(lst[n // 2:]) + rec(lst[:n // 2])

How can I find the time complexity of this function?

snatchysquid · Accepted Answer · 2020-09-12 07:13:16Z

1

Usually in such problems drawing the recursion tree helps.

Look at this photo I added, note how each level sums up to N (since slicing is the thing here doing the work), and the depth of the tree is logN (this is easy to show, since we divide by 2 each time, you can find an explanation here). So what we have is the function doing O(n) n*logn times which means in total we have O(n*logn).

Now another way of understanding this is using the "Master Theorem" (I encourage you to look it up and learn about it) We have here T(n) = 2T(n/2) + O(n), so according to the theorem a=2, b=2 so log_b(a) is equal to 1, and therefore we have (according to the 2nd case of the theorem):

T(n)=O(logn*(n**(log_b(a)))=O(nlogn)

answered Sep 12, 2020 at 7:13

snatchysquid

1,38212 silver badges25 bronze badges

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

Collectives™ on Stack Overflow

what is the time complexity of this recursive function in python?

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