Collections Big O

Question 1

Which ArrayList methods are guaranteed to run in constant time and which methods are guranteed to run in amortized constant time?

1. get
2. set
3. add
4. remove

Answer 1

Constant time:
1. get
2. set

Amortized constant time:
1. add
2. remove

Question 2

Is ArrayDeque likely to be faster than Stack when used as a stack and faster than LinkedList when used as a queue?

Answer 2

Yes

Question 3

Which methods are not guaranteed to run in amortized constant time for an ArrayDeque?

Answer 3

remove(obj), contains(obj), and the like, which run in linear time

Question 4

Which HashSet<E> methods guarantee constant time performance assuming the hash function disperses the elements properly among the buckets?

Answer 4

1. add()
2. remove()
3. contains()

Question 5

Which TreeSet<E> methods guarantee log(n) time performance?

Answer 5

1. add()
2. remove()
3. contains()

Question 6

Which HashMap<K, V> methods are guaranteed constant time performance assuming the hash function disperses the elements properly among the buckets?

Answer 6

1. get
2. containsKey
3. put
4. replace
5. remove

Question 7

Which TreeMap<K, V> methods guarantee log(n) time performance?

Answer 7

1. get
2. put
3. containsKey
4. remove
5. replace