scusate, ma solo dopo aver risposto ho relizzato che la domanda era relativa anche alle prestazioni in generale.
L'array, detto in parole povere è più "dispendioso": allocazione (in questo caso dinamica),accesso,ricerca e stampa. Cmq lo studi della complessità di un algoritmo va fatta nel suo complesso e si cerca di raggiungere un compromesso tra efficenza e progettazione