Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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);
}
like image 968
user2827214 Avatar asked Nov 02 '22 13:11

user2827214


1 Answers

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;
    }
}
like image 118
Origineil Avatar answered Nov 10 '22 02:11

Origineil