What's the time complexity of my accepted 8-line Python answer?


  • 0
    V
    class Solution:
        def findMin(self, num):
            head = 0
            tail = len(num) - 1
            while head < tail:
                #mid = (head + tail)/2  This line becomes useless
                if num[head] > num[tail]:
                    head = head + 1
                else:
                    tail = tail - 1
            return num[head]
    

    What's the time complexity of the code above? It's very similar to the code below, which is binary search solution to the problem Find Minimum in Rotated Sorted Array. Thanks in advance!

    class Solution:
        def findMin(self, num):
            head = 0
            tail = len(num) - 1
            while head < tail:
                mid = (head + tail)/2
                if num[mid] > num[tail]:
                    head = mid + 1
                else:
                    tail = mid
            return num[head]

  • 0
    D

    O(n). since head and tail are moved by only one step


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.