5

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);
}
Cole Tobin
  • 9,206
  • 15
  • 49
  • 74
user2827214
  • 1,191
  • 1
  • 13
  • 32
  • This question appears to be off-topic because it is about code complexity. – Cole Tobin Sep 28 '13 at 23:40
  • 1
    @ColeJohnson Borderline acceptable here, I don't think a closevote is in order for that reason. Granted, the question is simple though it has a basic attempt included. – nanofarad Sep 28 '13 at 23:42
  • @hexafraction Would Programmers or Code Review be a better option? – Cole Tobin Sep 28 '13 at 23:42
  • @ColeJohnson I believe that it would generally be acceptable here, and if it does poorly, Programmers may be the better option then. – nanofarad Sep 28 '13 at 23:44
  • 1
    It appears your judgement is accurate: ArrayList.remove(0) runs in O(n) and running it (n/2) times makes O(n^2). LinkedList.remove(0) runs in O(1) so this would be O(n). – Leo Izen Sep 29 '13 at 00:14
  • 1
    @ColeJohnson Questions about complexity are not necessarily off-topic; why do you think we have the tag? – arshajii Sep 29 '13 at 00:23
  • @arshajii I don't think they are off topic. That's the default "other" close reason text. I beleive they are borderline and think Programmers is the better option as Stack Overflow deals with "**problems** with code", not "time complexity of code". – Cole Tobin Sep 29 '13 at 00:25
  • @ColeJohnson Programmers.se is about concepts regarding software design and development. This is a specific question with concrete code. It is a good fit for SO. – arshajii Sep 29 '13 at 00:29
  • @arshajii fair enough. – Cole Tobin Sep 29 '13 at 00:34

1 Answers1

2

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;
    }
}
Community
  • 1
  • 1
Origineil
  • 3,108
  • 2
  • 12
  • 17