Time complexity of contains(Object o), in an ArrayList of Objects

java arraylist time-complexity
Samuel picture Samuel · Apr 24, 2011 · Viewed 43.2k times · Source

As the title says, I was wondering what the time complexity of the contains() method of an ArrayList is.

Answer

davin picture davin · Apr 24, 2011 
O(n)

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.

http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html

Related questions

Time complexity for java ArrayList

Is ArrayList an array or a list in java? what is the time complexity for the get operation, is it O(n) or O(1)?

Read More
Initialization of an ArrayList in one line

I wanted to create a list of options for testing purposes. At first, I did this: ArrayList<String> places = new ArrayList<String>(); places.add("Buenos Aires"); places.add("Córdoba"); places.add("La Plata"); Then, I …

Read More
Convert ArrayList<String> to String[] array

I'm working in the android environment and have tried the following code, but it doesn't seem to be working. String [] stockArr = (String[]) stock_list.toArray(); If I define as follows: String [] stockArr = {"hello", "world"}; it works. Is there something that …

Read More