we have this code
public int everDwindling(int m, int[] n) {
int pass = 0;
int[] seq = new int[m];
int ind = 0;
boolean isAllZero = false;
while(ind < n.length || !isAllZero) {
for(int i = 0 ; i < m && ind < n.length ; i ) {
if(seq[i] == 0) seq[i] = n[ind ];
}
int curMin = Integer.MAX_VALUE;
for(int i = 0 ; i < m ; i ) {
if(seq[i] < curMin && seq[i] > 0) curMin = seq[i];
}
int sum = 0;
for(int i = 0 ; i < m ; i ) {
seq[i]-=curMin;
sum =seq[i];
}
if(sum == 0) isAllZero = true;
pass ;
}
return pass;
}
so, this function wants to keep reducing the value of all integers and counts how many passes it needs to achieve that. Elements inside n is guaranteed to be greater than 0 and less than 2 billion. In my mind, the time complexity of this function is O(m*n.length), is this correct? and if not, could anyone elaborate? I'm always confused if pass
is going to affect time complexity calculation
CodePudding user response:
The worst case time is when the number of passes is maximised. This is when n.length
is greater than m
and in each pass (except the first) there is only one execution of ind
.
After the first pass, ind
will be equal to m
. After that ind
increases with just one in each pass in the worst case. So then the number of passes is then n.length - m 1
.
As each pass has a time complexity of O(m)
, that makes the worst case time complexity O((n.length - m 1)*m) = O(n.length*m)
The best case is when there is just one pass. This happens when m
is greater or equal to n.length
. In that case the complexity is O(m)
.