CODEWITHSUNDEEP
algorithmsearchbig-otime-complexity
7kemZmani
7kemZmani

Reputation: 649

Time complexity - O(n^2) to O(n log n) searching

I have an unordered list of n items, and I'm trying to find the most frequent item in that list. I wrote the following code:

def findFrequant(L):
     count = int()
     half = len(L)//2
     for i in L:
          for j in L:
               if i == j:
                    count += 1
                    if count > half:
                         msg = "The majority vote is {0}".format(i)
                         return msg
               else:
                    continue
          count = 0
     return "mixed list!"

Obviously this procedure with the two loops is O(n^2), and I'm trying to accomplish the same task in O(n log n) time. I'm not looking for a fix or someone to write the code for me, I'm simply looking for directions.

Upvotes: 0

Views: 217

Answers (2)

Joshua
Joshua

Reputation: 43280

I don't recognize the language here so I'm treating it as pseudocode.

This depends on a hashtable with key of the same type of element of L and value type of int. Count each record in hashtable, then iterate the hashtable as a normal collection of key,value pairs applying normal maxlist algorithm.

O(n) is slightly worse than linear. We remember that expense of a good hash is not linear but may be approximated as linear. Linear space used.

def findFrequant(L):
     hash = [,]
     vc = 0
     vv = null
     for i in L
         if hash.contains(i)
             hash[i] = hash[i] + 1
         else
             hash[i] = 1
     for (k,v) in hash
         if v > vc
             vv = k
             vc = v
         else if v == vc
             vv = null
     if (vv == null)
         return "mixed list!"
     else
         return "The majority vote is {0}".format(v)

Upvotes: 3

TmKVU
TmKVU

Reputation: 3000

You could use a Merge Sort, which has a worst case time complexity of O(n log(n)) and a binary search which has a worst case time complexity of O(log(n)).

There are sorting algorithms with faster best case scenarios, like for example bubble sort which has a best case of O(n), but merge sort performs in O(n log(n)) at it's worst, while bubble sort has a worst case of O(n^2).

Pessimistic as we Computer Scientists are, we generally analyze based on the worst-case scenario. Therefore a combination of merge sort and binary search is probably best in your case.

Note that in certain circumstances a Radix sort might perform faster than merge sort, but this is really dependent on your data.

Upvotes: 0

Related Questions