Why the cost of a built-in call matters
A single line such as list.contains(x) looks like one step, but the library does real work behind it. If that line sits inside a loop over n items and contains itself scans a list of n items, the program does about n * n steps, not n. When you estimate the time complexity of your own code, each call to a built-in method counts with its own cost. Knowing those costs lets you pick the right data structure before writing the code instead of finding out from a timeout.
The table below lists the costs of the operations used most often, for n elements in the collection or characters in the string.
| Operation | Time |
|---|---|
ArrayList.get(i), set(i, x), size() | O(1) |
ArrayList.add(x) at the end | O(1) amortized |
ArrayList.add(0, x), add(i, x), remove(i) | O(n) |
ArrayList.contains(x), indexOf(x), remove(Object) | O(n) |
LinkedList.addFirst, addLast, removeFirst, removeLast | O(1) |
LinkedList.get(i), contains(x) | O(n) |
ArrayDeque add or poll at either end | O(1) amortized |
HashMap and HashSet: get, put, containsKey, contains, remove | O(1) on average |
TreeMap and TreeSet: the same operations | O(log n) |
PriorityQueue: add, poll | O(log n) |
PriorityQueue: peek | O(1) |
PriorityQueue: contains, remove(Object) | O(n) |
String.length(), charAt(i) | O(1) |
String.equals, indexOf, contains, substring, toCharArray | O(n) |
StringBuilder.append | O(1) amortized per character |
Arrays.sort, Collections.sort | O(n log n) |
Arrays.binarySearch on a sorted array | O(log n) |
Arrays.fill, Arrays.copyOf, Collections.max, Collections.reverse | O(n) |
Lists: adding, removing and searching
These three operations are what the lesson asks about, and the answer depends on which list you use.
Adding. An ArrayList stores its elements in an array. Appending with add(x) writes into the next free slot. When the array is full, the list allocates a bigger one (about 1.5 times larger) and copies everything across, which costs O(n) once in a while. Spread over many appends, the average cost per append is constant, which is what "amortized O(1)" means. Inserting at the front or in the middle is different: every later element must shift one place, so add(0, x) is O(n).
Removing. remove(i) shifts everything after position i one place to the left, so it costs O(n), except for the last element, which needs no shifting. remove(Object) must also find the element first, which is a linear search. A LinkedList can unlink a node in O(1) once it holds it, but it has to walk the chain to find the node, so removing by value or by index is O(n) there as well.
Searching. Neither list is organised for lookup by value. contains and indexOf compare against elements one at a time using equals until they find a match, so the worst case, a missing element, checks all n. A HashSet answers the same question in O(1) on average, which is why the usual fix for a slow contains in a loop is to copy the values into a set first.
The reverse trade-off holds for positions. ArrayList.get(i) jumps straight to a slot, O(1), while LinkedList.get(i) follows links from one end, O(n). A loop that calls get(i) on a LinkedList is therefore O(n * n) overall. In practice, ArrayList is the right default, and ArrayDeque is better than LinkedList when you need a queue.
Maps, sets and heaps
A HashMap turns a key into an array position through its hashCode, so get and put do not search through the entries. The cost is O(1) on average. The average is not a guarantee: if many keys share a hash code, lookups slow down, although since Java 8 crowded buckets are organised as balanced trees to limit the damage. A TreeMap keeps its keys in sorted order in a balanced tree, so each operation takes O(log n), and in exchange it can answer questions that need order, such as the smallest key.
A PriorityQueue is a binary heap. Reading the smallest element with peek is O(1), but add and poll have to restore the heap shape and cost O(log n). It is not sorted internally, so searching it, with contains, is O(n).
Strings and sorting
Java strings are immutable. Every operation that seems to change one makes a new string, copying its characters, so substring and toCharArray are O(n) in the length they copy. This matters for concatenation in a loop: s += i copies the whole string each time, so building a string of n pieces this way takes O(n^2). A StringBuilder appends in place and brings the loop back to O(n):
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++) {
sb.append(i);
}
System.out.println(sb); // 01234
Sorting with Arrays.sort or Collections.sort takes O(n log n). Because comparing two strings costs up to the length of the shorter one, sorting n strings of length L costs O(n * L * log n), not O(n log n).
Gotchas
- The overloaded
remove. On aList<Integer>,remove(1)removes the element at index 1, whileremove(Integer.valueOf(1))removes the value 1. Both are O(n), but they do different things. With[10, 20, 30, 1], the first call leaves[10, 30, 1], and then the second leaves[10, 30]. - Hidden loops.
contains,indexOfandremove(Object)on a list are loops you did not write. Inside another loop they multiply. - Amortized is not worst case. A single
ArrayList.addcan take O(n) when the array grows. Only the average over many calls is constant. - Complexity says nothing about the constant. Two O(n) operations can differ in speed by a large factor, and the notation only describes how the time grows as
ngrows.
Key takeaways
- Count a built-in call as its own cost, not as one step.
- Lists search and remove in O(n); sets and maps do it in O(1) on average, or O(log n) when sorted.
- Use
ArrayListfor indexed access andArrayDequefor queues; appending is O(1) amortized, and inserting at the front is O(n). - Build strings with
StringBuilderin loops. - Sorting is O(n log n).
