Question

Describe at least three algorithms (python only) to determine whether an arbitrary array A[1 .. n] contains more than n/4 copies of any value. Analyze the running time complexity of all the three methods.

Answer 1

#---------- algos.py ------------
import random,time
#function that takes unsorted Array A
'''
Time complexity: O(n^2)
'''
def linearFinding(A):
   length = len(A)
   quarter = length//4
   #to store repeated values more than the quarter.
   vals = []
   #iterate through list
   for i in range(length):
       val_i = A[i]
       #set count of value at i to 1.
       count = 1
       #check the rest of the array
       #and get count.
       for j in range (i+1,length):
           if(val_i == A[j]):
               count+=1
       #if count is > quarter then
       if(count > quarter):
           #check if val_i not checked already.
           if(val_i not in vals):
               vals.append(val_i)
   print("\nValues that are repeated more than n/4(",quarter,") are: \n")
   length = len(vals)
   if(length == 0):
       print("\nNo values are there that are repeated")
       return 0
   for i in range(length):
       print(vals[i],end=" ")
   print("")
'''
Function that takes unsorted array.
Description: O(n log n)
'''
def sortedLinear(A):
   #copy the array A which takes O(N)
   A_copy = A.copy()
   #sort the array O(n log n)
   A_copy.sort()
  
   length = len(A_copy)
   quarter = length//4
   found = False
   print("\nValues that are repeated more than n/4(",quarter,") are: \n")
   i =0
   #iterate through array
   #below while loop overall time complexity will be O(N)
  
   while(i<length):
       #since the array is sorted.
       #all the values are in sequence.
       val_i = A_copy[i]
       #set count of val_i to 1.
       count = 1
       j = i+1
       #till j<length and j_th value is equal to val_i
       while(j<length and A_copy[j] == val_i):
           #increment count
           count+=1
           j+=1
       #if count > quarter
       if(count > quarter):
           #print it.
           print(val_i,end=" ")
           #since one value is found set found to true.
           found = True
           #increment the i by count
           i+=count
       else:
           #if not increment i by 1
           i+=1
   #if not found print no values are found
   if(not found):
       print("\nNo values are there that are repeated")
   print("")
  

'''
function that takes unsorted array.
Time Complexity: O(N)
'''
def dictSearch(A):
   vals = {}
   length = len(A)
   #iterate through list. O(N)
   for i in range(length):
       val_i = A[i]
       #time complexity of python dict.keys() is O(1)
       #you can check it.
       if(val_i in vals.keys()):
           #if val_i already is found then increment it by 1.
           vals[val_i] += 1
       else:
           #if not create new key by value 1.
           vals[val_i] = 1
  
   #then print the values in dictionary whose values are > count.
   #below opeartion depends on number of values that are repeated > quarter.
   #and it will be < O(N) so overall time complexity will be O(N) which is iterating
   #through list by using above for loop.
   quarter = length/4
   print("\nValues that are repeated more than n/4(",quarter,") are: \n")
   found = False
   for key,val in vals.items():
       if(val > quarter):
           print(key,end=" ")
           found = True
  
   if(not found):
       print("\nNo values are there that are repeated")
A = []
for i in range(10000):
   A.append(random.randint(0,3))
print("Array Size: ",len(A))

print("\n Method - 1")
st = time.time()
linearFinding(A)
end = time.time()- st
print("Time taken %.2f"%end)

print("\n Method - 2")
st = time.time()
sortedLinear(A)
end = time.time() - st
print("Time taken %.2f"%end)

print("\n Method - 3")
st = time.time()
dictSearch(A)
end = time.time() - st

print("Time taken %.2f"%end)