Какова временная сложность этого (простого) кода?

Question

Я пытаюсь выяснить время работы кода ниже, оба, если список был arraylist, и если это был связанный список. Я ценю любой совет!

Массив: Я подумал, что будет О (п) для операции удаления, и N/2 для контура, так что O (N^2)

LinkedList: только изменить ссылки, так что постоянное время для УДАЛИТЬ и N/2 для контура, так что о (п)

int halfSize = lst.size()/2; 

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

Answer 1

ArrayList: оценка верна, лежащая в основе из-за 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: оценка правильна, удаление индекса УЗЕЛ @zero постоянен

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; 
    } 
}