CODEWITHSUNDEEP
javatimecomplexity-theory
user2827214
user2827214

Reputation: 1191

What is the time complexity of this (simple) code?

I'm trying to figure out the running time of the code below, both if the list was an arraylist and if it was a linkedlist. I appreciate any advice!

Array: I thought it would be O(n) for remove operation, and N/2 for the loop, so O(n^2)

LinkedList: Only references change, so constant time for the remove and N/2 for the loop, so O(n)

int halfSize = lst.size() / 2;

for (int i = 0; i < halfSize; i++){
    lst.remove(0);
}

Upvotes: 5

Views: 481

Answers (1)

Origineil
Origineil

Reputation: 3118

ArrayList: evaluation correct, due to underlying array copy

    public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

LinkedList: evaluation correct, node removal @zero index is constant

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Upvotes: 2

Related Questions