This method merges two sorted lists and I want to know the time complexity of it if the length of list a is n and the length of list b is m. I am confused with while loops because they also sort of act like if statements (are only executed when the condition is true), meaning they aren't necessarily executed, so how can I compute the time complexity of them?

ArrayList<Integer> union(ArrayList<Integer> a, ArrayList<Integer> b){
        ArrayList<Integer> res = new ArrayList<>();
        int i = 0, j = 0;
        while (i<a.size() && j<b.size()){
            if(a.get(i) < b.get(j)){
                res.add(a.get(i));
                i  ;
            } else if (a.get(i) > b.get(j)){
                res.add(b.get(j));
                j  ;
            } else {
                res.add(b.get(j));
                i  ;
                j  ;
            }
        }
        while (i < a.size()){
            res.add(a.get(i));
            i  ;
        }
        while (j < b.size()){
            res.add(b.get(j));
            j  ;
        }
        return res;
    }

CodePudding user response：

Well, each iteration of each while loop increments either i or j (or both) by 1.

• i can grow from 0 to n - 1.
• j can group from 0 to m - 1.
• Hence the total number of iterations is bound by n m.

Since each iteration of any of the 3 loops does constant amount of work (since both ArrayList's get and add take constant time), the total time complexity in O(n m).

BTW, is this method supposed to eliminate duplicates?

If it does, it only eliminates duplicates for elements that appear on both input lists. If a list already contains duplicates, they won't be eliminated.

If it's not supposed to eliminate duplicates, it has a bug, since if a.get(i) == b.get(j), both should be added to the output list (since both i and j are incremented in this case).