Forelæsning 7/10 2003: Noget om hvorfor det er godt at kende til algoritmer og store O også selvom de fleste er skrevet i forvejen

Hvorfor kan vi ikke nøjes med ArrayList, den har da alle de metoder vi ska' bru'e?

add(...) er stort set O(1) - OK.
iterator fungerer uden for meget overhead.

Men:
add(...) er en gang imellem O(n) !!!!
contains(...), indexOf(...) er O(n) og ganget med konstant fra "equals"

Overvej: Hvis vi har en ArrayList (længde n) af ArrayLists (hver af gnst. lgd. m), hvad mon indexOf(...) koster??

Andre Collections så som HashSet og diverse SortedSets har bedre karakteristika.