In: Computer Science
Find the minimum element from the lists of integers with Java. 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. 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]
// 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:-
Note: please give me a positive rating thank you:)