Menu
As the title says, I was wondering what the time complexity of the contains() method of an ArrayList is.
408
Getting back to complexity analysis, the ArrayList. contains() method requires O(n) time. So the time we spend to find a specific object here depends on the number of items we have in the array.
Big O: Formal DefinitionLet T(n) – the number of operations performed in an algorithm as a function of n. T(n) ∈ O(f(n)) if and only if there exists two constants, n0 > 0 and c > 0 and a function f(n) such that for all n > n0 , cf(n) ≥ T(n).
It runs in O(1) expected time, as any hash table (assuming the hash function is decent). It is backed by a HashMap where the key is the Object.
O(n) The
size,isEmpty,get,set,iterator, andlistIteratoroperations run in constant time. Theaddoperation 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.
http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html
89
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
