CODEWITHSUNDEEP
algorithmwhile-loopbig-o
User
User

Reputation: 1726

What is the Big-O complexity of the following method?

I have a method below and I want to know the big O complexity.

public FinalPrepDeque<E> listUnion(FinalPrepDeque<E> lst2) {

          FinalPrepDeque<E> lst3 = new FinalPrepDeque<E>();

          Iterator<E> it1 = this.iterator();

          while (it1.hasNext()) { // O(n)
              E val = it1.next();
              if (val != null)
                  lst3.addLast(val);
          }

          Iterator<E> it2 = lst2.iterator();

          boolean found;
          while (it2.hasNext()) { // O(n)
            E val2 = it2.next();
            if (val2 != null) {

            found = false;
            it1 = this.iterator();

            while (it1.hasNext()) { // O(n)
              E val1 = it1.next();
              if (val1 != null) {
              if (val1.equals(val2)) {

                found = true;
                break;
              }
             }
            }
            if (!found)
              lst3.addLast(val2);

          }
          } // end outer-while

          return lst3;
        }

I know the first while loop as a complexity of O(n), and the second while loop has a complexity of O(n^2). In this case, do we drop the first O(n) and keep the second O(n^2) and say this method has a complexity of O(n^2)? Or do we keep it and say it has a complexity of O(n + n^2)?

Upvotes: 0

Views: 174

Answers (2)

Kjnokeer
Kjnokeer

Reputation: 97

With Big-O notation, you have:

n1 + n2 * n3 = n + n^2 = O(n + n^2) = O(n^2)

The n1 is your first while, the n2 is your second while and n3 is the third while into the second.

Upvotes: 1

Lawrence McAlpin
Lawrence McAlpin

Reputation: 2785

You keep the part with the largest growth rate, so O(n^2).

Upvotes: 1

Related Questions