Runtime complexity of exhaustive search?


  • 0
    P

    I'm curious what the runtime complexity would be of a naïve exhaustive search algorithm.

    Here is an example:

    def maxNumberExhaustive(self, nums1, nums2, k, current, best):
            if len(current) == k: 
                if self.listCompare(current, best):
                    best[:] = current
                return
            elif len(current) < k:
                for i in xrange(len(nums1)):
                    current.append(nums1[i])
                    self.maxNumberExhaustive(nums1[i+1::], nums2, k, current, best)
                    current.pop()
                for i in xrange(len(nums2)):
                    current.append(nums2[i])
                    self.maxNumberExhaustive(nums1, nums2[i+1::], k, current, best)
                    current.pop()
    

    Would it be m+n choose k, i.e. the number of subsets of length k from m + n elements?

    (I know this is not an efficient solution, I'm just having trouble analyzing the brute force solution)


Log in to reply
 

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