31

I found other entries for this question that dealt with specific methods, but nothing comprehensive. I'd like to verify my own understanding of the most often used methods of this data structure:

O(1) - Constant Time:

isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)

O(N) - Linear Time:

indexof(x)
clear()
remove(x)
remove(i)

Is this correct? Thanks for your help.

Alex35
  • 73
  • 1
  • 5
dvanaria
  • 6,593
  • 22
  • 62
  • 82

1 Answers1

37

The best resource is straight from the official API:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

brian_d
  • 11,190
  • 5
  • 47
  • 72
  • That does help, thanks. I see now why add(x, i) would run in linear time (worst case) because it may have to move a bunch of elements higher in the array to insert a new one. Same with remove(i). What's the difference between amortized constant time and regular constant time? – dvanaria Jun 30 '11 at 21:36
  • @dvanaria Some good answers about amortized constant time are at this post http://stackoverflow.com/questions/200384/constant-amortized-time. Basically, the average time is constant, but each individual operation may take more time - in this case when the underlying array has to resize. – brian_d Jun 30 '11 at 21:52