How do I calculate the time complexity of while loops with nested if conditions?

user_19520285 0
Viewed 45

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;
    }
big-o time-complexity java
1 Answers

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

user_12215710
Related