CODEWITHSUNDEEP
javatime-complexity
user1995200
user1995200

Reputation: 29

complexity class

What is the big O notation for this problem? Why? I think it's O(N) because we have one loop here but I'm not sure.

public static void mystery(List<String> list){

    for(int i = 0; i< list.size()-1; i+=2){

        String first = list.remove(i);

        list.add(i + 1, first);

    }

}

Upvotes: 1

Views: 418

Answers (3)

Kyle
Kyle

Reputation: 1019

The time complexity is O(n^2).

The loop will execute floor(n/2) times. List.add(int i) and list.remove(int i) are both O(n) on average(see the notes on why below). This results in O(n*n/2) which is O(n^2).

Some notes on built in List implementations

When calling List.add(int i, element) or List.remove(int i) on an ArrayList, elements in the list must be shifted to insert or remove an element(when not at the end of the list) On average the number of shifts necessary is n. Thus the add and remove operations are both O(n).

List.add(int i, element) and List.remove(int i) are also O(n) when called on a LinkedList. This is due to the need to traverse to the given index in order to remove/add an element.

We can do better when we know that adds/remove to a given List will be sequential. A ListIterator, using a LinkedList, can be used to reduce the time complexity to O(n). The add and remove methods are O(1) when invoked on a LinkedLists ListIterator as there's no need to traverse to the given index.

Sample implementation of the askers method using ListIterator

public static void mystery(List<String> list){
    ListIterator<String> iterator = list.listIterator();
    int i = 0;
    while (i < list.size()-1) {
        String first = iterator.next();
        // Remove first
        iterator.remove();
        // Skip an element
        iterator.next();
        // insert at i+1
        iterator.add(first);
        i+=2;
    }
}

Upvotes: 3

hqt
hqt

Reputation: 30276

When running this method, it will excute:

remove 0
append 1
remove 1
append 2
...

Assume List is Array List:

assume all remove elements always at last So: n/2 * (2*n + n) = 3 * n^2 /2 => O(n^2)

assume all remove elements always at top. So: n/2 * (n + n) => O(n^2)

So. because the worst case and best case always O(n^2), so, not only Big-O, but the complexity will be o(n^2).

Upvotes: 0

William Rookwood
William Rookwood

Reputation: 327

It looks like it's O(n^2). It iterates through a list, and for each iteration, it calls list.remove() which also runs in O(n). Therefore the time complexity for this function should be O(n^2).

Upvotes: 0

Related Questions