0

How can I find the time complexity of this function:

def f(lst, d, u):
    # assume 0<=d<=u<n where n is the length of the list
    if lst[d] == lst[u]:
        return u-d
    return max(f(lst, d+1, u), f(lst, d, u-1))

What this function does is find the largest value which appears twice in the list in the range between d and u

bendaMan
  • 43
  • 7
  • In the worst case (i.e. all values in `lst` are different), It's exponential in u-d, specifically O(2**(u-d)). – Tom Karzes Sep 10 '20 at 06:10
  • @TomKarzes are you sure its not n**2? – bendaMan Sep 10 '20 at 06:11
  • See the [Wiki](https://wiki.python.org/moin/TimeComplexity)! – Klaus D. Sep 10 '20 at 06:11
  • 1
    @bendaMan Very sure. Each time you increase u-d by one, you double the number of calls. It's a textbook case of exponential growth. – Tom Karzes Sep 10 '20 at 06:11
  • 2
    @KlausD. how is it relevant? – bendaMan Sep 10 '20 at 06:12
  • @TomKarzes acceptable. how can this be shown? – bendaMan Sep 10 '20 at 06:13
  • 1
    @bendaMan `O(n**2)` usually happens with nested for loops. In this case, it's more like `O(2**n)` since you have to compute two branches for each call of `f`. – Mateen Ulhaq Sep 10 '20 at 06:13
  • It states the average and worst case time complexity of all kind of Python functions. – Klaus D. Sep 10 '20 at 06:13
  • @KlausD. but here its a custom recursive function, I don't think wiki talks about that – bendaMan Sep 10 '20 at 06:14
  • 1
    @bendaMan If you increase u-d by one, then you make *two* recursive calls with the lower value of u-d. It doubles each time you increase u-d by one. The call tree is a binary tree whose depth is u-d. – Tom Karzes Sep 10 '20 at 06:14
  • @TomKarzes I think I'm getting there, could you try explaining this a bit more? – bendaMan Sep 10 '20 at 06:15
  • @MateenUlhaq can I visualize this by drawing a tree somehow? – bendaMan Sep 10 '20 at 06:16
  • @MateenUlhaq so if I draw a tree of calls if I add one I create a new root which has a left tree (say the original one) and now another one about the same size? – bendaMan Sep 10 '20 at 06:18
  • @bendaMan just draw a binary tree. Each node has two children. The depth is u-d. I don't think it can be explained any more clearly. Again, that's the worst-case time complexity. If the list contains long runs of the same value, it will be faster. If the list contains only a single repeated value, then the function will return immediately. – Tom Karzes Sep 10 '20 at 06:18
  • @TomKarzes the only point unclear is why is the depth u-d? – bendaMan Sep 10 '20 at 06:19
  • @bendaMan The leaf level occurs when u == d. In that case, it's comparing a single value to itself and it returns 0. One level up occurs when u = d+1. In that case it calls itself twice, with each call having u == d. And so on. – Tom Karzes Sep 10 '20 at 06:21
  • Also, how is the restriction `0<=d<=u – Mateen Ulhaq Sep 10 '20 at 06:21
  • @TomKarzes ok I understand now, Thank you! – bendaMan Sep 10 '20 at 06:21
  • 2
    @MateenUlhaq Only the difference between u and d matters in the worst case. The recursive calls each reduce that difference by one. When it reaches zero, the function is guaranteed to return with no further calls. Write it out on paper if you need to. – Tom Karzes Sep 10 '20 at 06:22
  • By the way, this function returns the maximum distance between two elements that have the same value. It *could* be implemented in O((u-d)**2) time, but it wasn't, so this is a very inefficient way to do it. – Tom Karzes Sep 10 '20 at 06:26
  • By the way, if you want to see the exponential runtime, call it like this: `f(list(range(100)), 0, 99)` Good luck waiting for it to terminate. – Tom Karzes Sep 10 '20 at 06:28
  • Does this answer your question? [How efficient is Python's max function](https://stackoverflow.com/questions/5454030/how-efficient-is-pythons-max-function) – Josh Bowden Sep 10 '20 at 08:11

0 Answers0