We have this code
public void min(List<List<Integer>> lists) {
int count = lists.size();
int[] ind = new int[count]; //keeps track of traversal progress of each list
int done = 0;
while(done != count) {
done = 0;
int min = Integer.MAX_VALUE;
int minListIndex = -1;
for(int i = 0 ; i < count ; i++) {
List<Integer> curList = lists.get(i);
if(ind[i] >= curList.size()) {
done++;
continue;
}
int curElement = curList.get(ind[i]);
if(curElement < min) {
min = curElement;
minListIndex = i;
}
}
if(minListIndex > -1) ind[minListIndex]++;
}
}
in a glance, time complexity of this method is O(n) where n is sum(curList.size()). however, since each element may be scanned n times (at worst), will this make the complexity O(n^2) instead of O(n)?