Độ phức tạp về thời gian chứa (Object o), trong ArrayList của các đối tượng

Question

Khi tiêu đề cho biết tôi đã tự hỏi độ phức tạp của phương thức contains() của ArrayList là gì.

Answer 1

O(n) 

Các size, isEmpty, get, set, iterator, và listIterator hoạt động chạy trong thời gian không đổi. Hoạt động add chạy trong thời gian không đổi hằng số, nghĩa là thêm các phần tử n yêu cầu thời gian O (n). Tất cả các hoạt động khác chạy trong thời gian tuyến tính (gần như nói). Các yếu tố không đổi là thấp so với điều đó cho việc thực hiện LinkedList.

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

Answer 2

đó là O (n) cho ArrayList