The question basically says it all. Suppose I have a (sorted) list that can contain anywhere from 1K to 1M items. I have a starting index and an ending index. If I use the ArrayList.sublist(start, end) method, is the time complexity O(n) or O(1)? I did check for answers here since I'd think would be a common question, but although I found a duplicate answer for a LinkedList, I couldn't find a specific question about ArrayList. Thanks to all for their answers!
Asked
Active
Viewed 6,625 times
7
user207421
- 305,947
- 44
- 307
- 483
Grace F.
- 73
- 1
- 3
-
3@IlyaBursov No. There is no copy step. See the Javadoc. The time complexity is *O(1)*. – user207421 May 15 '18 at 01:13
-
@EJP you're right, I've completely forgot about that – Iłya Bursov May 15 '18 at 01:14
1 Answers
19
The sub-list is backed by the source list. There is no copy step, so the time complexity is O(1).
user207421
- 305,947
- 44
- 307
- 483