-1
def mystery(mylist, first, last):
     if (first == last):
        return mylist[first]
     mid = (first + last) // 2
     return min(mystery(mylist, first, mid), mystery(mylist, mid+1, last))

Is it $O(logN)$ because every time the array size becomes half and called again?

Avishek Saha
  • 1
  • 1
  • 3
    O(n), you halve the size of the array but you also double the invocations, basically canceling each other out. – luk2302 Nov 19 '22 at 01:53
  • 2
    You can get some hints just by doing some experiments with a counter. – President James K. Polk Nov 19 '22 at 02:10
  • Does this answer your question? [How can I find the time complexity of an algorithm?](https://stackoverflow.com/questions/11032015/how-can-i-find-the-time-complexity-of-an-algorithm) – Welbog Nov 19 '22 at 02:33
  • The `return mylist[first]` happens exactly N times, and the `return min(...)` statement happens exactly N-1 times. There's exactly 2N-1 calls to `mystery` (including the original call). – Paul Hankin Nov 19 '22 at 09:11
  • @Welbog no this doesn't answer my question. – Avishek Saha Nov 21 '22 at 05:26

1 Answers1

0

You can count exactly the operations in this function. First, one must observe that this function finds the smallest element in mylist between first and last.

We can see that return mylist[first] happens exactly once for each element of the input array, so happens exactly N times overall.

The second return (ie: return min(...)) chooses the smallest of the smallest of each half of the array. Each element in the array (except for the smallest element) is on the losing side of this min exactly once, so this statement occurs exactly N-1 times overall.

There's 2 calls to mystery for each execution of the second return statement, and none for the first return statement, and each call to mystery executes one or the other, so the total number of calls to mystery (including the initial call) is 1 + 2(N-1) = 2N-1.

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118