algo complexity - ever dwindling value from a series of integers

caballeros 0
Viewed 24

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

time-complexity algorithm
1 Answers

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).

trincot0
Related