What's the complexity from this code? And what notation do I have to use?

Question

When I determine the complexity of a Java code like this , do I have to express that in a Theta or a big O notation?

List<Person> sortedPersons = new ArrayList<Person>();
List<Person> people = new ArrayList<Person>();

    for (int i = 0; i < people.size(); i++) {
        Person toadd = people.get(i);

        int index = 0;
        while(index < sortedPersons.size() && sortedPersons.get(index).compareTo(toadd) < 0)
            index++;

        sortedPersons.add(index, toadd);

    }

I know the for-loop is O(n) (or is it \Theta(n)?) A get-operation runs in constant time, so O(1). But what about the while loop? sortedPersons.size(): O(1) sortedPersons.get(): O(1) Is the compareTo-operation linear? And I think the add-operation also runs in constant time. What's the total complexity of the code?

Answer 1

the code is O(n²) If you consider numbers and you sort them from small to large.

• If your input is reverse sorted (from large to small), the code will be Θ(n).
• If your input is already sorted, this code will be Θ(n²)

The code is just a variant of Insertion sort, it just uses a list instead of an array.

Consider this example for the complexity:

The numbers are 1 2 3 4 5 and you want to sort from small to big.

1. After first itteration your list will consist of 1. (this happens in o(1) ) and you won t visit the inner loop.
2. In the second itteration you have a list of { 1 } since you are inserting 2 you 'll visit the while loop once, after it you 'll insert it.
3. Third itteration the list is { 1 2 } you visit the while loop twice and insert 3 after it.
4. ...

In the end you will have something like: 0 1 2 3 4 time's visited the inner loop.

Now you can write 1 2 3 4 5 as (5(5+1))/2).

Now you can write O(n(n+1) / 2 + n) as O(n²).