Complessità di ArrayList e LinkedList

1. Supponiamo che un metodo Java riceva un elenco e inverta l'ordine degli elementi in esso contenuti rimuovendo ciascun elemento dalla parte anteriore dell'elenco, aggiungendo ogni elemento a uno stack e quindi rimuovendo gli elementi dallo stack e inserendo ciascun elemento in la fine della lista. Qual è il tempo di esecuzione previsto per il Big-O se viene passato un ArrayList , un LinkedList .

ArrayList è O (N ^ 2) perché la rimozione di ogni elemento richiede che gli elementi precedenti siano spostati verso l'alto, che richiede tempo O (N) e che ci sono N iterazioni. LinkedList è O (N) poiché i puntatori mobili richiedono O (1) tempo, con N iterazioni.

2. Qual è il tempo di esecuzione di Big-O del seguente frammento di codice? Supponi che lst1 abbia N elementi, e lst2 sia inizialmente vuoto.

   public static void add( List<Integer> lst1, List<Integer> lst2){

   for ( Integer x : lst1 )
   lst2.add(0, x);  // add to front
   }
   

ArrayList è O (N ^ 2) perché l'aggiunta in primo piano richiede lo spostamento degli altri elementi verso il basso, che richiede tempo O (N), e ci sono N iterazioni. LinkedList è O (N) poiché l'aggiunta al fronte richiede solo O (1) tempo, con N iterazioni.

Idealmente mi piacerebbe sapere suggerimenti per arrivare a una risposta corretta dai miei dispositivi se ci sono risposte sbagliate.