Question

You will find the minimum element from the lists of integers.

Input: [[5,2,31,9],[2,1,6,7,11],[55,0,7,8,9]]

Output: 0. [The minimum among the lists of integers]

1. Implement a program of O(N^k) runtime complexity of the problem. marks   50

2. Implement a program of ~ O(N*logN) runtime complexity of the above same problem and explain how you have achieved. [Hint : Apply the log rule -> sort the list of integers, then compare the first element of each] marks   50

Total   100

You can choose either C#, Python, Java to implement 1 & 2.

Answer 1

// python

// first will take n^k where n is the number of elements in the list and k is total list since we are accessing the all elements

// for second question we are sorting each list and one list will take to sort nlogn time so to sort all list it will take knlogn as there are k list to sort. and now to compare all elements with zeroth element of every ;list will take k time so knlogn+k so overall time complexity =knlogn.

# minimum from list of list
def findMinimum(numbers):
  minimum=999999999
  for i in range(len(numbers)):
    for j in range(len(numbers[i])):
      if minimum>numbers[i][j]:
        minimum=numbers[i][j]

  return minimum

def findMinimumUsingSorting(numbers):
  minimum=999999999
  for i in range(len(numbers)):
    numbers[i].sort()
    if minimum>numbers[i][0]:
      minimum=numbers[i][0]

  return minimum


numbers=[[5,2,31,9],[2,1,6,7,11],[55,0,7,8,9]]
print('Minimum using linear search: ',findMinimum(numbers))
print('Minimum using sorting: ',findMinimumUsingSorting(numbers))

// Sample output:-