Complexity¶
Every method of a collection whose cost depends on the size documents that cost in its javadoc. This page is generated from the javadoc, so it matches the code. Hover a cell to read the whole note.
Legend¶
n is the size of the receiver, m the size of the argument, k the number of elements taken, dropped or skipped, i an index. The Scala column gives the abbreviation Scala's collections documentation uses for the same class, where there is one.
| Class | Scala | Meaning | Expressions |
|---|---|---|---|
| constant | C |
a fixed number of steps, whatever the size | O(1) |
| effectively constant | eC |
a walk down a tree of 32-wide nodes, a handful of levels deep at any size (Vector, HashSet, HashMap) | effectively O(1) |
| amortised constant | aC |
constant on average over a series of calls; now and then one call takes O(n) (Queue) | amortised O(1) |
| logarithmic | Log |
O(log n): one walk from the root of a balanced tree | O(log n) |
| lazy | nothing is computed now; each element is computed when it is read (the note says what is computed at once) | lazy |
|
| linear | L |
proportional to the number of elements named in the expression | O(k), O(m), O(n), O(index), O(m + n), O(n + k), O(n + m), O(endIndex), O(from + k), O(n / size), O(n / step), O(index + m), O(k + log n), O(max(n, m)), O(min(n, m)), O(beginIndex), O(length - k), O(offset + m), O(min(i, n - i)), O(m + min(i, n - i)), effectively O(min(n, size - n)) |
| n log n | a sort, or one tree operation per element | O(m log n), O(n log n), O(m + n log n), O(n + r log n), O(m log(n + m)), O((n + m) log n), O((n / size) log n), O((n / step) log n) |
|
| polynomial | a product of sizes: a slice search, a matrix, a cartesian product | O(n^2), O(n * m), O(n^power), O(n * size), O(rows * columns), O(n * size / step), O(n + (n / step) * min(size, n - size)) |
|
| combinatorial | one result per permutation or combination | O(n!), O(2^n), O(n! * n), O(C(n, k)) |
"Effectively" and "amortised" are not the same promise:
- Effectively constant is a worst case: it grows with the size, but so slowly that it stays a handful of steps.
- Amortised constant is an average: most calls are constant, and an occasional call pays for the others.
A lazy note describes what the call itself does; reading the result costs more.
n/a means the type does not have the operation: HashSet and HashMap have no positional methods, because their order is not defined.
Sequences¶
NonEmptyVector wraps a Vector, so its costs are Vector's; Stream is lazy, so most of its operations are deferred until the result is read.
| Operation | Vector |
List |
Queue |
Stream |
NonEmptyVector |
|---|---|---|---|---|---|
head |
effectively O(1) | O(1) | O(1) | O(1) | effectively O(1) |
tail |
effectively O(1) | O(1) | amortised O(1) | O(1) | effectively O(1) |
last |
effectively O(1) | O(n) | O(n) | O(n) | effectively O(1) |
init |
effectively O(1) | O(n) | amortised O(1) | lazy | effectively O(1) |
get |
effectively O(1) | O(index) | O(index) | O(index) | effectively O(1) |
update |
effectively O(1) | O(index) | O(n) | O(index) | effectively O(1) |
prepend |
effectively O(1) | O(1) | O(1) | O(1) | effectively O(1) |
append |
effectively O(1) | O(n) | amortised O(1) | O(1) | effectively O(1) |
prependAll |
O(m) | O(m) | O(m) | O(1) | O(m) |
appendAll |
O(m) | O(n + m) | O(m) | O(1) | O(m) |
insert |
O(min(i, n - i)) | O(index) | O(n) | lazy | n/a |
removeAt |
O(min(i, n - i)) | O(index) | O(n) | lazy | O(min(i, n - i)) |
take |
effectively O(1) | O(n) | O(n) | lazy | effectively O(1) |
drop |
effectively O(1) | O(n) | O(n) | O(n) | effectively O(1) |
slice |
effectively O(1) | O(endIndex) | O(n) | O(beginIndex) | effectively O(1) |
splitAt(Predicate<? super T>) |
O(k) | O(k) | O(n) | O(k) | n/a |
splitAt(int) |
effectively O(1) | O(n) | O(n) | O(n) | n/a |
reverse |
O(n) | O(n) | O(n) | O(n) | O(n) |
sorted |
O(n log n) | O(n log n) | O(n log n) | O(n log n) | O(n log n) |
length |
O(1) | O(n) | O(n) | O(n) | n/a |
contains |
O(n) | O(n) | O(n) | O(n) | O(n) |
indexOf |
O(n) | O(n) | O(n) | O(n) | O(n) |
zip |
O(min(n, m)) | O(min(n, m)) | O(min(n, m)) | lazy | O(min(n, m)) |
sliding(int) |
O(n) | O(n * size) | O(n * size) | lazy | n/a |
sliding(int, int) |
O(n / step) | O(n * size / step) | O(n * size / step) | lazy | n/a |
grouped |
O(n / size) | O(n) | O(n) | lazy | O(n / size) |
distinct |
O(n) | O(n) | O(n) | lazy | O(n) |
concat |
n/a | n/a | n/a | n/a | O(m) |
Sets¶
head, take and drop exist only where the order is defined: insertion order on LinkedHashSet, the comparator's order on TreeSet.
| Operation | HashSet |
LinkedHashSet |
TreeSet |
|---|---|---|---|
contains |
effectively O(1) | effectively O(1) | O(log n) |
add |
effectively O(1) | effectively O(1) | O(log n) |
remove |
effectively O(1) | effectively O(1) | O(log n) |
union |
O(m) | O(m) | O(m log(n + m)) |
intersect |
O(n + m) | O(n + m) | O((n + m) log n) |
diff |
O(n + m) | O(n + m) | O((n + m) log n) |
min |
O(n) | O(n) | O(n) |
max |
O(n) | O(n) | O(n) |
head |
n/a | effectively O(1) | O(log n) |
take |
n/a | effectively O(min(n, size - n)) | O(log n) |
drop |
n/a | effectively O(min(n, size - n)) | O(log n) |
Maps¶
As for the sets, only the ordered maps have positional methods.
| Operation | HashMap |
LinkedHashMap |
TreeMap |
|---|---|---|---|
get |
effectively O(1) | effectively O(1) | O(log n) |
containsKey |
effectively O(1) | effectively O(1) | O(log n) |
put |
effectively O(1) | effectively O(1) | O(log n) |
remove |
effectively O(1) | effectively O(1) | O(log n) |
keySet |
O(n) | O(1) | O(n log n) |
values |
O(n) | O(n) | O(n) |
head |
n/a | effectively O(1) | O(log n) |
take |
n/a | effectively O(min(n, size - n)) | O(log n) |
drop |
n/a | effectively O(min(n, size - n)) | O(log n) |
Every documented method¶
The notes as the javadoc states them, per type, in declaration order. A type that inherits a note says so.
Vector¶
| Method | Cost | Note |
|---|---|---|
transpose(Vector<Vector<T>>) |
O(rows * columns) | O(rows * columns); the matrix itself is returned when it has no or one element. |
flatten(Iterable<? extends Iterable<? extends T>>) |
O(n) | O(n) for n inner elements in total, one builder append each. |
append(T) |
effectively O(1) | effectively O(1) (a path copy; the last leaf is copied). |
appendAll(Iterable<? extends T>) |
O(m) | O(m) for m appended elements (one leaf copy per 32 elements plus a path copy); O(1) when this Vector is empty and iterable is a Vector, which is returned as is. |
asJava() |
O(1) | O(1); get on the view is effectively O(1), and so is each step of its iterator. |
combinations() |
O(2^n) | O(2^n) combinations, each of size up to n. |
combinations(int) |
O(C(n, k)) | O(C(n, k)) combinations of size k. |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
distinct() |
O(n) | O(n). |
distinctBy(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctBy(Function<? super T, ? extends U>) |
O(n) | O(n). |
duplicates() |
O(n) | O(n), one hash lookup per element. |
duplicatesBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key and one hash lookup per element. |
distinctByKeepLast(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctByKeepLast(Function<? super T, ? extends U>) |
O(n) | O(n). |
drop(int) |
effectively O(1) | effectively O(1) (the path to the new first leaf is trimmed). |
dropUntil(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) drop. |
dropWhile(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) drop. |
dropRight(int) |
effectively O(1) | effectively O(1) (the path to the new last leaf is trimmed). |
dropRightUntil(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) take. |
dropRightWhile(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) take. |
endsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that. |
foldRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n), walking the elements from the last to the first without copying. |
get(int) |
effectively O(1) | effectively O(1) (O(log32 n) trie access). |
head() |
effectively O(1) | effectively O(1). |
indexOf(T) |
O(n) | O(n). |
indexOf(T, int) |
O(n) | O(n). |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
indexWhere(Predicate<? super T>) |
O(n) | O(n). |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
init() |
effectively O(1) | effectively O(1) (the path to the last leaf is trimmed). |
initOption() |
effectively O(1) | effectively O(1) (one init). |
insert(int, T) |
O(min(i, n - i)) | O(min(i, n - i)): the shorter side is re-appended or re-prepended element by element. |
insertAll(int, Iterable<? extends T>) |
O(m + min(i, n - i)) | O(m + min(i, n - i)) for m inserted elements. |
intersperse(T) |
O(n) | O(n). |
iterator() |
O(1) | O(1) to create; each step is O(1) within a leaf and effectively O(1) at a leaf boundary. |
last() |
effectively O(1) | effectively O(1). |
lastIndexOf(T) |
O(n) | O(n). |
lastIndexOf(T, int) |
O(n) | O(n). |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n). |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
length() |
O(1) | O(1); the length is a field of the trie. |
padTo(int, T) |
O(k) | O(k) for the k elements appended. |
leftPadTo(int, T) |
O(k) | O(k) for the k elements prepended. |
patch(int, Iterable<? extends T>, int) |
O(n + m) | O(n + m) for m elements of that. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n), one builder append per element. |
permutations() |
O(n! * n) | O(n! * n) in the worst case (all elements distinct). |
prefixLength(Predicate<? super T>) |
O(k) | O(k) for a prefix of k elements. |
prepend(T) |
effectively O(1) | effectively O(1) (a path copy; the first leaf is copied). |
prependAll(Iterable<? extends T>) |
O(m) | O(m) for m prepended elements (one leaf copy per 32 elements plus a path copy); O(1) when this Vector is empty and iterable is a Vector, which is returned as is. |
remove(T) |
O(n) | O(n). |
removeFirst(Predicate<T>) |
O(n) | O(n). |
removeLast(Predicate<T>) |
O(n) | O(n). |
removeAt(int) |
O(min(i, n - i)) | O(min(i, n - i)): the shorter side is re-appended or re-prepended element by element. |
removeAll(T) |
O(n) | O(n). |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements. |
removeAll(Predicate<? super T>) |
O(n) | O(n). |
replace(T, T) |
O(n) | O(n) to find the element, then one effectively O(1) update. |
replaceAll(T, T) |
O(n) | O(n) plus one effectively O(1) update per occurrence. |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m retained elements (they are hashed once, then one filter pass). |
reverse() |
O(n) | O(n). |
rotateLeft(int) |
O(k) | O(k) for the k = n mod length elements moved to the end. |
rotateRight(int) |
O(length - k) | O(length - k) for k = n mod length: the elements before the moved suffix are re-appended. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
O(n) | O(n). |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n). |
search(T) |
O(log n) | O(log n) comparisons, each an effectively O(1) access. |
search(T, Comparator<? super T>) |
O(log n) | O(log n) comparisons, each an effectively O(1) access. |
segmentLength(Predicate<? super T>, int) |
O(k) | O(k) for a run of k elements. |
shuffle() |
O(n) | O(n). |
slice(int, int) |
effectively O(1) | effectively O(1) (the paths to the new first and last leaves are trimmed). |
sorted() |
O(n log n) | O(n log n) comparisons; the elements are copied to an array, sorted there and regrouped into leaves. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons; the elements are copied to an array, sorted there and regrouped into leaves. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
span(Predicate<? super T>) |
O(k) | O(k) for k elements before the split, then an effectively O(1) split. |
splitAt(int) |
effectively O(1) | effectively O(1). |
splitAt(Predicate<? super T>) |
O(k) | O(k) for k elements before the split, then an effectively O(1) split. |
splitAtInclusive(Predicate<? super T>) |
O(k) | O(k) for k elements up to the split, then an effectively O(1) split. |
startsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that. |
startsWith(Iterable<? extends T>, int) |
O(m) | O(m) for m elements of that. |
subSequence(int) |
effectively O(1) | effectively O(1). |
subSequence(int, int) |
effectively O(1) | effectively O(1). |
tail() |
effectively O(1) | effectively O(1) (the path to the first leaf is trimmed). |
tailOption() |
effectively O(1) | effectively O(1) (one tail). |
take(int) |
effectively O(1) | effectively O(1) (the path to the new last leaf is trimmed). |
takeUntil(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) take. |
takeWhile(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) take. |
takeRight(int) |
effectively O(1) | effectively O(1) (the path to the new first leaf is trimmed). |
takeRightUntil(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) drop. |
takeRightWhile(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) drop. |
unzip(Function<? super T, Tuple2<? extends T1, ? extends T2>>) |
O(n) | O(n). |
unzip3(Function<? super T, Tuple3<? extends T1, ? extends T2, ? extends T3>>) |
O(n) | O(n). |
update(int, T) |
effectively O(1) | effectively O(1) (a path copy; the leaf holding the element is copied). |
update(int, Function<? super T, ? extends T>) |
effectively O(1) | effectively O(1) (one access and one path copy). |
zip(Iterable<? extends U>) |
O(min(n, m)) | O(min(n, m)) for m elements of that. |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for m elements of that. |
zipAll(Iterable<? extends U>, T, U) |
O(max(n, m)) | O(max(n, m)) for m elements of that. |
zipWithIndex() |
O(n) | O(n). |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
O(n) | O(n). |
grouped(int) |
O(n / size) | O(n / size) blocks, each an effectively O(1) slice sharing this Vector's leaves. |
sliding(int) |
O(n) | O(n) windows, each an effectively O(1) slice sharing this Vector's leaves. |
sliding(int, int) |
O(n / step) | O(n / step) windows, each an effectively O(1) slice sharing this Vector's leaves. |
slideBy(Function<? super T, ?>) |
O(n) | O(n); each run is an effectively O(1) slice sharing this Vector's leaves. |
crossProduct() |
O(n^2) | O(n^2); the pairs are built now. |
crossProduct(int) |
O(n^power) | O(n^power) Vectors of size power, built now. |
crossProduct(Iterable<? extends U>) |
O(n * m) | O(n * m) for m elements of that; the pairs are built now. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n), walking the elements from the last to the first without copying. |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested. |
headOption() |
effectively O(1) | effectively O(1), that of head(). |
lastOption() |
effectively O(1) | effectively O(1), that of last(). |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
size() |
O(1) | O(1), that of length(). |
contains(T) (from Traversable) |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |
List¶
| Method | Cost | Note |
|---|---|---|
flatten(Iterable<? extends Iterable<? extends T>>) |
O(n) | O(n) for n inner elements in total: one cell per element, built reversed and reversed once. |
transpose(List<List<T>>) |
O(rows * columns) | O(rows * columns). |
append(T) |
O(n) | O(n); every cell of this List is rebuilt. |
appendAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m appended elements; the elements are copied once and this List is rebuilt. |
asJava() |
O(1) | O(1); get(i) on the view is O(i), size() is O(1). |
combinations() |
O(2^n) | O(2^n) combinations. |
combinations(int) |
O(C(n, k)) | O(C(n, k)) combinations. |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
distinct() |
O(n) | O(n). |
distinctBy(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key per element. |
distinctByKeepLast(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctByKeepLast(Function<? super T, ? extends U>) |
O(n) | O(n), one key per element. |
drop(int) |
O(n) | O(n) for n dropped elements; the rest of this List is shared, not copied. |
dropUntil(Predicate<? super T>) |
O(k) | O(k) for the k dropped elements; the rest of this List is shared, not copied. |
dropWhile(Predicate<? super T>) |
O(k) | O(k) for the k dropped elements; the rest of this List is shared, not copied. |
dropRight(int) |
O(n) | O(n); the kept prefix is copied. |
dropRightUntil(Predicate<? super T>) |
O(n) | O(n); the List is reversed twice. |
dropRightWhile(Predicate<? super T>) |
O(n) | O(n); the List is reversed twice. |
duplicates() |
O(n) | O(n), one hash lookup per element. |
duplicatesBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key and one hash lookup per element. |
endsWith(Iterable<? extends T>) |
O(n + m) | O(n + m) for m elements of that: the suffix is reached by walking this List. |
filter(Predicate<? super T>) |
O(n) | O(n). |
get(int) |
O(index) | O(index); the cells are walked one by one. |
indexOf(T) |
O(n) | O(n). |
indexOf(T, int) |
O(n) | O(n). |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
indexWhere(Predicate<? super T>) |
O(n) | O(n). |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
init() |
O(n) | O(n); the kept prefix is copied. |
initOption() |
O(n) | O(n); the kept prefix is copied. |
length() |
O(n) | O(n); a cons list has no length field, so the cells are counted. |
insert(int, T) |
O(index) | O(index); the cells before the insertion point are copied, the rest is shared. |
insertAll(int, Iterable<? extends T>) |
O(index + m) | O(index + m) for m inserted elements; the cells before the insertion point are copied, the rest is shared. |
intersperse(T) |
O(n) | O(n). |
last() |
O(n) | O(n). |
lastIndexOf(T) |
O(n) | O(n). |
lastIndexOf(T, int) |
O(n) | O(n). |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n). |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
padTo(int, T) |
O(n + k) | O(n + k) for k added elements. |
leftPadTo(int, T) |
O(k) | O(k) for k added elements; this List is shared, not copied. |
patch(int, Iterable<? extends T>, int) |
O(n + m) | O(n + m) for m replacement elements. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n); each side is built reversed and reversed once. |
peek() |
O(1) | O(1); the head is a field of the cons cell. |
peekOption() |
O(1) | O(1); the head is a field of the cons cell. |
permutations() |
O(n!) | O(n!) permutations. |
pop() |
O(1) | O(1); the tail is a field of the cons cell. |
popOption() |
O(1) | O(1); the tail is a field of the cons cell. |
pop2() |
O(1) | O(1); the head and the tail are fields of the cons cell. |
pop2Option() |
O(1) | O(1); the head and the tail are fields of the cons cell. |
prefixLength(Predicate<? super T>) |
O(k) | O(k) for the k elements of that prefix. |
prepend(T) |
O(1) | O(1); this List becomes the tail of one new cell. |
prependAll(Iterable<? extends T>) |
O(m) | O(m) for m prepended elements; this List is shared, not copied. |
push(T) |
O(1) | O(1); this List becomes the tail of one new cell. |
push(T[]) |
O(m) | O(m) for m pushed elements; this List is shared, not copied. |
pushAll(Iterable<T>) |
O(m) | O(m) for m pushed elements; this List is shared, not copied. |
remove(T) |
O(k) | O(k) for the k elements before the removed one; the rest of this List is shared, not copied. |
removeFirst(Predicate<T>) |
O(k) | O(k) for the k elements before the removed one; the rest of this List is shared, not copied. |
removeLast(Predicate<T>) |
O(n) | O(n); the List is reversed twice. |
removeAt(int) |
O(index) | O(index); the cells before the removed one are copied, the rest is shared. |
removeAll(T) |
O(n) | O(n). |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m removed elements (they are hashed once, then one filter pass). |
removeAll(Predicate<? super T>) |
O(n) | O(n). |
replace(T, T) |
O(k) | O(k) for the k elements before the replaced one; the rest of this List is shared, not copied. |
replaceAll(T, T) |
O(n) | O(n). |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m retained elements (they are hashed once, then one filter pass). |
reverse() |
O(n) | O(n). |
rotateLeft(int) |
O(n) | O(n); O(1) for n == 0, which is answered without walking the elements. |
rotateRight(int) |
O(n) | O(n); O(1) for n == 0, which is answered without walking the elements. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
O(n) | O(n). |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n); the elements are walked from the end. |
search(T) |
O(n) | O(n). |
search(T, Comparator<? super T>) |
O(n) | O(n). |
segmentLength(Predicate<? super T>, int) |
O(from + k) | O(from + k) for the k elements of that run. |
shuffle() |
O(n) | O(n). |
slice(int, int) |
O(endIndex) | O(endIndex). |
sorted() |
O(n log n) | O(n log n) comparisons. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
span(Predicate<? super T>) |
O(n) | O(n). |
splitAt(int) |
O(n) | O(n); the prefix is copied, the suffix is shared. |
splitAt(Predicate<? super T>) |
O(k) | O(k) for the k elements before the split; the suffix is shared. |
splitAtInclusive(Predicate<? super T>) |
O(k) | O(k) for the k elements up to the split; the suffix is shared. |
startsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that. |
startsWith(Iterable<? extends T>, int) |
O(offset + m) | O(offset + m) for m elements of that. |
subSequence(int) |
O(beginIndex) | O(beginIndex); the result shares the cells of this List. |
subSequence(int, int) |
O(endIndex) | O(endIndex). |
tail() |
O(1) | O(1); the tail is a field of the cons cell. |
tailOption() |
O(1) | O(1); the tail is a field of the cons cell. |
take(int) |
O(n) | O(n) for n taken elements; the prefix is copied. |
takeUntil(Predicate<? super T>) |
O(k) | O(k) for the k taken elements. |
takeWhile(Predicate<? super T>) |
O(k) | O(k) for the k taken elements. |
takeRight(int) |
O(n) | O(n); the List is reversed twice. |
takeRightUntil(Predicate<? super T>) |
O(n) | O(n); the List is reversed twice. |
takeRightWhile(Predicate<? super T>) |
O(n) | O(n); the List is reversed twice. |
update(int, T) |
O(index) | O(index); the cells before it are copied, the rest is shared. |
update(int, Function<? super T, ? extends T>) |
O(index) | O(index); the element is read, then the cells before it are copied. |
zip(Iterable<? extends U>) |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
zipAll(Iterable<? extends U>, T, U) |
O(max(n, m)) | O(max(n, m)) for an argument of m elements. |
zipWithIndex() |
O(n) | O(n). |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
O(n) | O(n). |
head() |
O(1) | O(1). |
iterator() |
O(1) | O(1) to create, O(1) per step. |
grouped(int) |
O(n) | O(n); each block is copied into its own List. |
sliding(int) |
O(n * size) | O(n * size); each window is copied into its own List. |
sliding(int, int) |
O(n * size / step) | O(n * size / step); each window is copied into its own List. |
slideBy(Function<? super T, ?>) |
O(n) | O(n); each run is copied into its own List. |
crossProduct() |
O(n^2) | O(n^2); the pairs are built now. |
crossProduct(int) |
O(n^power) | O(n^power) Lists of size power, built now. |
crossProduct(Iterable<? extends U>) |
O(n * m) | O(n * m) for m elements of that; the pairs are built now. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n); the List is reversed first. |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested. |
headOption() |
O(1) | O(1), that of head(). |
lastOption() |
O(n) | O(n), that of last(). |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
size() |
O(n) | O(n), that of length(). |
contains(T) (from Traversable) |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |
Queue¶
| Method | Cost | Note |
|---|---|---|
flatten(Iterable<? extends Iterable<? extends T>>) |
O(n) | O(n) for n inner elements in total: they are collected into the front list of the result. |
transpose(Queue<Queue<T>>) |
O(rows * columns) | O(rows * columns). |
enqueue(T) |
O(1) | O(1); the element is prepended to the rear list. |
enqueueAll(Iterable<? extends T>) |
O(m) | O(m) for m enqueued elements. |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
endsWith(Iterable<? extends T>) |
O(n + m) | O(n + m) for m elements of that. |
indexOf(T) |
O(n) | O(n). |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
indexWhere(Predicate<? super T>) |
O(n) | O(n). |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
lastIndexOf(T) |
O(n) | O(n). |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n). |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
prefixLength(Predicate<? super T>) |
O(k) | O(k) for the k elements of that prefix. |
search(T) |
O(n) | O(n). |
search(T, Comparator<? super T>) |
O(n) | O(n). |
segmentLength(Predicate<? super T>, int) |
O(from + k) | O(from + k) for the k elements of that run. |
startsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that. |
append(T) |
amortised O(1) | amortised O(1); the element is prepended to the rear list. |
appendAll(Iterable<? extends T>) |
O(m) | O(m) for m appended elements. |
asJava() |
O(1) | O(1); get(i) on the view is O(i), size() is O(1). |
combinations() |
O(2^n) | O(2^n) combinations. |
combinations(int) |
O(C(n, k)) | O(C(n, k)) combinations. |
distinct() |
O(n) | O(n). |
distinctBy(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key per element. |
duplicates() |
O(n) | O(n), one hash lookup per element. |
duplicatesBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key and one hash lookup per element. |
distinctByKeepLast(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctByKeepLast(Function<? super T, ? extends U>) |
O(n) | O(n), one key per element. |
drop(int) |
O(n) | O(n); the front and the rear are both walked. |
dropWhile(Predicate<? super T>) |
O(n) | O(n). |
dropRight(int) |
O(n) | O(n); the front and the rear are both walked. |
dropRightUntil(Predicate<? super T>) |
O(n) | O(n). |
dropRightWhile(Predicate<? super T>) |
O(n) | O(n). |
filter(Predicate<? super T>) |
O(n) | O(n). |
get(int) |
O(index) | O(index) while the index is in the front; O(n) once it falls in the rear, which is measured and indexed from its end. |
head() |
O(1) | O(1); the head of the front list. |
indexOf(T, int) |
O(n) | O(n). |
init() |
amortised O(1) | amortised O(1); the last element is the head of the rear list, unless the rear is empty and the front is walked. |
insert(int, T) |
O(n) | O(n); the front, and the rear when the index falls in it, are walked. |
insertAll(int, Iterable<? extends T>) |
O(n + m) | O(n + m) for m inserted elements. shared. |
intersperse(T) |
O(n) | O(n). |
iterator() |
O(m) | O(m) to create, for the m elements of the rear list, which is reversed; then O(1) per step. |
last() |
O(n) | O(n) when the rear is empty and the front is walked; O(1) when the rear is non-empty. |
lastIndexOf(T, int) |
O(n) | O(n). |
length() |
O(n) | O(n); the front and the rear are counted. |
padTo(int, T) |
O(n + k) | O(n + k) for k added elements. |
leftPadTo(int, T) |
O(n + k) | O(n + k) for k added elements. |
patch(int, Iterable<? extends T>, int) |
O(n + m) | O(n + m) for m replacement elements. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n); each side is built reversed and becomes the front list of its Queue. |
permutations() |
O(n!) | O(n!) permutations. |
prepend(T) |
O(1) | O(1); the element is prepended to the front list. |
prependAll(Iterable<? extends T>) |
O(m) | O(m) for m prepended elements. |
remove(T) |
O(n) | O(n). |
removeFirst(Predicate<T>) |
O(n) | O(n). |
removeLast(Predicate<T>) |
O(n) | O(n). |
removeAt(int) |
O(n) | O(n). |
removeAll(T) |
O(n) | O(n). |
replace(T, T) |
O(n) | O(n). |
replaceAll(T, T) |
O(n) | O(n). |
reverse() |
O(n) | O(n). |
rotateLeft(int) |
O(n) | O(n); O(1) for n == 0, which is answered without walking the elements. |
rotateRight(int) |
O(n) | O(n); O(1) for n == 0, which is answered without walking the elements. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
O(n) | O(n). |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n). |
shuffle() |
O(n) | O(n). |
slice(int, int) |
O(n) | O(n). |
sorted() |
O(n log n) | O(n log n) comparisons. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
span(Predicate<? super T>) |
O(n) | O(n). |
splitAt(int) |
O(n) | O(n). |
splitAt(Predicate<? super T>) |
O(n) | O(n). |
splitAtInclusive(Predicate<? super T>) |
O(n) | O(n). |
startsWith(Iterable<? extends T>, int) |
O(offset + m) | O(offset + m) for m elements of that. |
subSequence(int) |
O(n) | O(n). |
subSequence(int, int) |
O(n) | O(n). |
tail() |
amortised O(1) | amortised O(1); the front loses its head, and the rear is reversed onto it only when the front runs out. |
take(int) |
O(n) | O(n). |
takeUntil(Predicate<? super T>) |
O(n) | O(n). |
takeRight(int) |
O(n) | O(n). |
takeRightUntil(Predicate<? super T>) |
O(n) | O(n). |
takeRightWhile(Predicate<? super T>) |
O(n) | O(n). |
update(int, T) |
O(n) | O(n). |
update(int, Function<? super T, ? extends T>) |
O(n) | O(n). |
zip(Iterable<? extends U>) |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
zipAll(Iterable<? extends U>, T, U) |
O(max(n, m)) | O(max(n, m)) for an argument of m elements. |
zipWithIndex() |
O(n) | O(n). |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
O(n) | O(n). |
dequeue() |
amortised O(1) | amortised O(1); see tail(). |
dequeueOption() |
amortised O(1) | amortised O(1); see dequeue(). |
enqueue(T[]) |
O(m) | O(m) for m enqueued elements. |
peek() |
O(1) | O(1); the head of the front list. |
peekOption() |
O(1) | O(1); the head of the front list. |
dropUntil(Predicate<? super T>) |
O(n) | O(n). |
initOption() |
amortised O(1) | amortised O(1); see init(). |
tailOption() |
amortised O(1) | amortised O(1); see tail(). |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m retained elements (they are hashed once, then one filter pass). |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m removed elements (they are hashed once, then one filter pass). |
removeAll(Predicate<? super T>) |
O(n) | O(n). |
takeWhile(Predicate<? super T>) |
O(n) | O(n). |
grouped(int) |
O(n) | O(n); each block is copied into its own Queue. |
sliding(int) |
O(n * size) | O(n * size); each window is copied into its own Queue. |
sliding(int, int) |
O(n * size / step) | O(n * size / step); each window is copied into its own Queue. |
slideBy(Function<? super T, ?>) |
O(n) | O(n); each run is copied into its own Queue. |
crossProduct() |
O(n^2) | O(n^2); the pairs are built now. |
crossProduct(int) |
O(n^power) | O(n^power) Queues of size power, built now. |
crossProduct(Iterable<? extends U>) |
O(n * m) | O(n * m) for m elements of that; the pairs are built now. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n); the elements are walked once as a List, in reverse. |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested. |
headOption() |
O(1) | O(1), that of head(). |
lastOption() |
O(n) | O(n), that of last(). |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
size() |
O(n) | O(n), that of length(). |
contains(T) (from Traversable) |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |
Stream¶
| Method | Cost | Note |
|---|---|---|
concat(Iterable<? extends T>[]) |
O(k) | O(k) for k iterables, whose iterators are obtained now; the elements are lazy. |
concat(Iterable<? extends Iterable<? extends T>>) |
O(k) | O(k) for k iterables, whose iterators are obtained now; the elements are lazy. |
flatten(Iterable<? extends Iterable<? extends T>>) |
lazy | lazy; the first element is found when this method is called (skipping the empty inner iterables before it), each further one when the result reaches it. An outer iterable with infinitely many empty inner ones and no element after them never yields, so the call does not return. |
transpose(Stream<Stream<T>>) |
O(rows * columns) | O(rows * columns); the whole matrix is forced. |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements; the elements are forced until the slice is found. |
endsWith(Iterable<? extends T>) |
O(n + m) | O(n + m) for m elements of that; the whole Stream is forced. |
indexOf(T) |
O(n) | O(n); the elements are forced until the element is found. |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements; the elements are forced until the slice is found. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements; the elements are forced until the slice is found. |
indexWhere(Predicate<? super T>) |
O(n) | O(n); the elements are forced until one satisfies the predicate. |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n); the elements are forced until one satisfies the predicate. |
lastIndexOf(T) |
O(n) | O(n); the whole Stream is forced. |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements; the whole Stream is forced. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements; the elements up to end are forced. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n); the whole Stream is forced. |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n); the elements up to end are forced. |
prefixLength(Predicate<? super T>) |
O(k) | O(k); the k elements of that prefix are forced, plus the first one that is not. |
search(T) |
O(n) | O(n); the elements are forced until one is not smaller than element. |
search(T, Comparator<? super T>) |
O(n) | O(n); the elements are forced until one is not smaller than element. |
segmentLength(Predicate<? super T>, int) |
O(from + k) | O(from + k); the elements of that run are forced, plus the first one that is not. |
startsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that; only those elements are forced. |
startsWith(Iterable<? extends T>, int) |
O(offset + m) | O(offset + m) for m elements of that; only those elements are forced. |
append(T) |
O(1) | O(1); the head is forced, the rest of this Stream stays deferred and the element is reached last. |
appendAll(Iterable<? extends T>) |
O(1) | O(1); the head of this Stream and of elements is forced, the rest stays deferred. |
appendSelf(Function<? super Stream<T>, ? extends Stream<T>>) |
O(1) | O(1); the result is built lazily and each element is forced when it is reached. |
asJava() |
O(1) | O(1); the view forces no element ahead of the read that needs it: get(i) forces the first i + 1 elements, the iterator one element per step, and size(), lastIndexOf, hashCode, getLast and every read of reversed() force the whole Stream (they do not terminate on an infinite Stream). |
combinations() |
O(2^n) | O(2^n) combinations; the whole Stream is forced. |
combinations(int) |
O(C(n, k)) | O(C(n, k)) combinations; the whole Stream is forced. |
cycle() |
O(1) | O(1); the result is infinite and each element is forced when it is reached. |
cycle(int) |
lazy | lazy; each element is forced when the result reaches it. |
distinct() |
lazy | lazy; each element is forced and hashed when the result reaches it. |
distinctBy(Comparator<? super T>) |
lazy | lazy; O(log n) comparisons per element when the result reaches it. |
distinctBy(Function<? super T, ? extends U>) |
lazy | lazy; one key per element when the result reaches it. |
duplicates() |
O(n) | O(n), one hash lookup per element; the whole Stream is forced, so it does not terminate on an infinite Stream (whether an element repeats, and so whether it comes before the next one, is known only at the end). |
duplicatesBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key and one hash lookup per element; the whole Stream is forced, so it does not terminate on an infinite Stream. |
distinctByKeepLast(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons; the whole Stream is forced, because the last occurrence decides. |
distinctByKeepLast(Function<? super T, ? extends U>) |
O(n) | O(n), one key per element; the whole Stream is forced, because the last occurrence decides. |
drop(int) |
O(n) | O(n); the first n elements are forced, the rest stays deferred. |
dropUntil(Predicate<? super T>) |
O(k) | O(k); the k skipped elements are forced, the rest stays deferred. |
dropWhile(Predicate<? super T>) |
O(k) | O(k); the k skipped elements are forced, the rest stays deferred. |
dropRight(int) |
lazy | lazy; the result runs n elements behind this Stream, so it works on an infinite Stream. |
dropRightUntil(Predicate<? super T>) |
O(n) | O(n); the whole Stream is forced, because the last matching element decides. |
dropRightWhile(Predicate<? super T>) |
O(n) | O(n); the whole Stream is forced, because the last matching element decides. |
filter(Predicate<? super T>) |
lazy | lazy; the elements are forced until the first match, the rest on demand. |
get(int) |
O(index) | O(index); the first index + 1 elements are forced. |
indexOf(T, int) |
O(n) | O(n); the elements are forced until the element is found. |
init() |
lazy | lazy; the result runs one element behind this Stream, so only the first two elements are forced. |
initOption() |
lazy | lazy; see init(). |
insert(int, T) |
lazy | lazy; the first index elements are forced when the result reaches them. |
insertAll(int, Iterable<? extends T>) |
lazy | lazy; the first index elements are forced when the result reaches them. |
intersperse(T) |
lazy | lazy; one element is forced, the rest on demand. |
last() |
O(n) | O(n); the whole Stream is forced, so it does not terminate on an infinite Stream. |
lastIndexOf(T, int) |
O(n) | O(n); the elements up to end are forced. |
length() |
O(n) | O(n); the whole Stream is forced, so it does not terminate on an infinite Stream. |
padTo(int, T) |
lazy | lazy; the padding is appended without forcing this Stream. |
leftPadTo(int, T) |
O(n) | O(n); the whole Stream is forced, because its length decides how much padding is needed. |
patch(int, Iterable<? extends T>, int) |
lazy | lazy; the elements are forced as the result reaches them. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
lazy | lazy; as every Stream is head-strict, each side is forced to its first element when this method is called, and each further element of a side is found when that side reaches it. The results of f that one side has passed stay memoised until the other side has passed them too. On an infinite Stream, a side that never receives an element is searched forever, so the call does not return (as with partition). |
permutations() |
O(n!) | O(n!) permutations; the whole Stream is forced. |
prepend(T) |
O(1) | O(1); nothing is forced. |
prependAll(Iterable<? extends T>) |
O(1) | O(1); the head of this Stream is forced, the rest stays deferred. |
remove(T) |
lazy | lazy; the elements are forced until the first occurrence, the rest on demand. |
removeFirst(Predicate<T>) |
lazy | lazy; the elements are forced until the first match, the rest on demand. |
removeLast(Predicate<T>) |
O(n) | O(n); the whole Stream is forced, because the last match decides. |
removeAt(int) |
lazy | lazy; the first index elements are forced when the result reaches them. |
removeAll(T) |
lazy | lazy; each element is forced when the result reaches it. |
removeAll(Iterable<? extends T>) |
lazy | lazy; the removed elements are hashed once, then each element is forced when the result reaches it. |
removeAll(Predicate<? super T>) |
lazy | lazy; each element is forced when the result reaches it. |
replace(T, T) |
lazy | lazy; the elements are forced until the first occurrence, the rest on demand. |
replaceAll(T, T) |
lazy | lazy; each element is forced when the result reaches it. |
retainAll(Iterable<? extends T>) |
lazy | lazy; the retained elements are hashed once, then each element is forced when the result reaches it. |
reverse() |
O(n) | O(n); the whole Stream is forced. |
rotateLeft(int) |
O(n) | O(n); the whole Stream is forced, because its length decides the rotation. n == 0 is O(1) and forces nothing, so it works on an infinite Stream. |
rotateRight(int) |
O(n) | O(n); the whole Stream is forced, because its length decides the rotation. n == 0 is O(1) and forces nothing, so it works on an infinite Stream. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
lazy | lazy; each element is forced when the result reaches it. |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
lazy | lazy; each element is forced when the result reaches it. |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n); the whole Stream is forced, because the fold starts at the end. |
shuffle() |
O(n) | O(n); the whole Stream is forced. |
slice(int, int) |
O(beginIndex) | O(beginIndex); the elements up to beginIndex are forced, the rest when the result reaches them, so it works on an infinite Stream. |
sorted() |
O(n log n) | O(n log n) comparisons; the whole Stream is forced. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons; the whole Stream is forced. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the whole Stream is forced. The key is recomputed at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the whole Stream is forced. The key is recomputed at every comparison. |
span(Predicate<? super T>) |
O(k) | O(k); the k elements of the prefix are forced, the suffix stays deferred. |
splitAt(int) |
O(n) | O(n); the first n elements are forced, the suffix stays deferred. |
splitAt(Predicate<? super T>) |
O(k) | O(k); the k elements before the split are forced, the suffix stays deferred. |
splitAtInclusive(Predicate<? super T>) |
O(k) | O(k); the k elements up to the split are forced, the suffix stays deferred. |
subSequence(int) |
O(beginIndex) | O(beginIndex); the elements before beginIndex are forced, the rest stays deferred. |
subSequence(int, int) |
O(beginIndex) | O(beginIndex); the elements before beginIndex are forced, the rest when the result reaches them. |
tail() |
O(1) | O(1); the tail is forced when it is asked for, and memoised. |
tailOption() |
O(1) | O(1); see tail(). |
take(int) |
lazy | lazy; O(1), one element is forced and the rest on demand. |
takeUntil(Predicate<? super T>) |
lazy | lazy; each element is forced when the result reaches it. |
takeWhile(Predicate<? super T>) |
lazy | lazy; each element is forced when the result reaches it. |
takeRight(int) |
O(n) | O(n); the whole Stream is forced, because the last n elements decide. |
takeRightUntil(Predicate<? super T>) |
O(n) | O(n); the whole Stream is forced, because the last matching element decides. |
takeRightWhile(Predicate<? super T>) |
O(n) | O(n); the whole Stream is forced, because the last matching element decides. |
update(int, T) |
O(index) | O(index); the first index + 1 elements are forced. |
update(int, Function<? super T, ? extends T>) |
O(index) | O(index); the first index + 1 elements are forced. |
zip(Iterable<? extends U>) |
lazy | lazy; O(min(n, m)) pairs when consumed. |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
lazy | lazy; O(min(n, m)) results when consumed. |
zipAll(Iterable<? extends U>, T, U) |
lazy | lazy; O(max(n, m)) pairs when consumed. |
zipWithIndex() |
lazy | lazy; each element is forced when the result reaches it. |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
lazy | lazy; each element is forced when the result reaches it. |
extend(T) |
O(1) | O(1); the result is infinite and each element is forced when it is reached. |
extend(Supplier<? extends T>) |
O(1) | O(1); the result is infinite and each element is forced when it is reached. |
extend(Function<? super T, ? extends T>) |
O(1) | O(1); the result is infinite and each element is forced when it is reached. |
head() |
O(1) | O(1). |
grouped(int) |
lazy | lazy; a block is built when the result reaches it and its elements are forced when the block is consumed, so an infinite Stream can be grouped. Whether a further block exists is decided when the result's tail is reached, which forces one element past the end of the block. |
sliding(int) |
lazy | lazy; a window is built when the result reaches it and its elements are forced when the window is consumed, so an infinite Stream can be windowed. Whether a further window exists is decided when the result's tail is reached, which forces up to max(size, step) + 1 elements past the window's start. |
sliding(int, int) |
lazy | lazy; a window is built when the result reaches it and its elements are forced when the window is consumed, so an infinite Stream can be windowed. Whether a further window exists is decided when the result's tail is reached, which forces up to max(size, step) + 1 elements past the window's start. |
slideBy(Function<? super T, ?>) |
lazy | lazy; the first run is built now, each further run when the result reaches it; a run is forced whole, up to the first element of the next one. |
crossProduct() |
lazy | lazy; O(n^2) pairs when consumed. |
crossProduct(int) |
lazy | lazy; O(n^power) Streams of size power when consumed. |
crossProduct(Iterable<? extends U>) |
lazy | lazy; O(n * m) pairs when consumed. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n); the whole Stream is forced and reversed. |
max() |
O(n) | O(n), every element compared once; the whole Stream is forced, so it does not terminate on an infinite Stream. |
min() |
O(n) | O(n), every element compared once; the whole Stream is forced, so it does not terminate on an infinite Stream. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested. |
headOption() |
O(1) | O(1), that of head(). |
lastOption() |
O(n) | O(n), that of last(). |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
size() |
O(n) | O(n), that of length(). |
contains(T) (from Traversable) |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |
NonEmptyVector¶
| Method | Cost | Note |
|---|---|---|
append(A) |
effectively O(1) | effectively O(1), that of Vector#append(Object). |
appendAll(Vector<? extends A>) |
O(m) | O(m) for m appended elements, that of Vector#appendAll(Iterable). |
appendAll(NonEmptyVector<? extends A>) |
O(m) | O(m) for m appended elements, that of Vector#appendAll(Iterable). |
concat(NonEmptyVector<? extends A>) |
O(m) | O(m) for m appended elements, that of appendAll(NonEmptyVector). |
prepend(A) |
effectively O(1) | effectively O(1), that of Vector#prepend(Object). |
prependAll(Vector<? extends A>) |
O(m) | O(m) for m prepended elements, that of Vector#prependAll(Iterable). |
prependAll(NonEmptyVector<? extends A>) |
O(m) | O(m) for m prepended elements, that of Vector#prependAll(Iterable). |
reverse() |
O(n) | O(n), that of Vector#reverse(). |
distinct() |
O(n) | O(n), that of Vector#distinct(). |
distinctBy(Comparator<? super A>) |
O(n log n) | O(n log n) comparisons, that of Vector#distinctBy(Comparator). |
distinctBy(Function<? super A, ? extends K>) |
O(n) | O(n), that of Vector#distinctBy(Function). |
sorted() |
O(n log n) | O(n log n) comparisons, that of Vector#sorted(). |
sorted(Comparator<? super A>) |
O(n log n) | O(n log n) comparisons, that of Vector#sorted(Comparator). |
sortBy(Function<? super A, ? extends U>) |
O(n log n) | O(n log n) comparisons, that of Vector#sortBy(Function). |
sortBy(Comparator<? super U>, Function<? super A, ? extends U>) |
O(n log n) | O(n log n) comparisons, that of Vector#sortBy(Comparator,. |
zip(NonEmptyVector<? extends B>) |
O(min(n, m)) | O(min(n, m)) for m elements of that, that of Vector#zip(Iterable). |
zipWith(NonEmptyVector<? extends B>, BiFunction<? super A, ? super B, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for m elements of that, that of Vector#zipWith(Iterable,. |
zipWithIndex() |
O(n) | O(n), that of Vector#zipWithIndex(). |
zipWithIndex(BiFunction<? super A, ? super Integer, ? extends B>) |
O(n) | O(n), that of Vector#zipWithIndex(BiFunction). |
scanLeft(B, BiFunction<? super B, ? super A, ? extends B>) |
O(n) | O(n), that of Vector#scanLeft(Object,. |
update(int, A) |
effectively O(1) | effectively O(1), that of Vector#update(int,. |
update(int, Function<? super A, ? extends A>) |
effectively O(1) | effectively O(1), that of Vector#update(int,. |
grouped(int) |
O(n / size) | O(n / size) blocks, each an effectively O(1) slice, that of Vector#grouped(int). |
duplicates() |
O(n) | O(n), that of Vector#duplicates(). |
duplicatesBy(Function<? super A, ? extends K>) |
O(n) | O(n), that of Vector#duplicatesBy(Function). |
tail() |
effectively O(1) | effectively O(1), that of Vector#tail(). |
init() |
effectively O(1) | effectively O(1), that of Vector#init(). |
drop(int) |
effectively O(1) | effectively O(1), that of Vector#drop(int). |
dropRight(int) |
effectively O(1) | effectively O(1), that of Vector#dropRight(int). |
dropWhile(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, that of Vector#dropWhile(Predicate). |
dropUntil(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, that of Vector#dropUntil(Predicate). |
dropRightWhile(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, that of Vector#dropRightWhile(Predicate). |
dropRightUntil(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, that of Vector#dropRightUntil(Predicate). |
take(int) |
effectively O(1) | effectively O(1), that of Vector#take(int). |
takeRight(int) |
effectively O(1) | effectively O(1), that of Vector#takeRight(int). |
takeWhile(Predicate<? super A>) |
O(k) | O(k) for k taken elements, that of Vector#takeWhile(Predicate). |
takeUntil(Predicate<? super A>) |
O(k) | O(k) for k taken elements, that of Vector#takeUntil(Predicate). |
takeRightWhile(Predicate<? super A>) |
O(k) | O(k) for k taken elements, that of Vector#takeRightWhile(Predicate). |
takeRightUntil(Predicate<? super A>) |
O(k) | O(k) for k taken elements, that of Vector#takeRightUntil(Predicate). |
slice(int, int) |
effectively O(1) | effectively O(1), that of Vector#slice(int,. |
removeAt(int) |
O(min(i, n - i)) | O(min(i, n - i)), that of Vector#removeAt(int). |
remove(A) |
O(n) | O(n), that of Vector#remove(Object). |
removeAll(A) |
O(n) | O(n), that of Vector#removeAll(Object). |
removeAll(Iterable<? extends A>) |
O(n + m) | O(n + m) for m given elements, that of Vector#removeAll(Iterable). |
removeAll(Predicate<? super A>) |
O(n) | O(n), that of Vector#removeAll(Predicate). |
head() |
effectively O(1) | effectively O(1), that of Vector#head(). |
last() |
effectively O(1) | effectively O(1), that of Vector#last(). |
max(Comparator<? super A>) |
O(n) | O(n), every element compared once. |
min(Comparator<? super A>) |
O(n) | O(n), every element compared once. |
get(int) |
effectively O(1) | effectively O(1), that of Vector#get(int). |
contains(A) |
O(n) | O(n). |
indexOf(A) |
O(n) | O(n). |
iterator() |
O(1) | O(1) to create; each step is O(1) within a leaf and effectively O(1) at a leaf boundary. |
asJava() |
O(1) | O(1); get on the view is effectively O(1). |
HashSet¶
| Method | Cost | Note |
|---|---|---|
flatten(Iterable<? extends Iterable<? extends T>>) |
O(n) | O(n) for n inner elements in total, one effectively O(1) insertion each. |
add(T) |
effectively O(1) | effectively O(1) (one hash lookup, then a path copy of the trie when the element is new). |
addAll(Iterable<? extends T>) |
O(m) | O(m) for m elements, each an effectively O(1) insertion; O(1) when this set is empty and elements is a HashSet, which is returned as is. |
contains(T) |
effectively O(1) | effectively O(1) (one hash lookup). |
diff(Set<? extends T>) |
O(n + m) | O(n + m) for a set of m elements (a hash set of them, then one filter pass). |
intersect(Set<? extends T>) |
O(n + m) | O(n + m) for a set of m elements (the smaller set is filtered against a hash set of the larger one). |
iterator() |
O(1) | O(1) to create; a whole walk is O(n). |
asJava() |
O(1) | O(1); contains on the view is effectively O(1). |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n), one effectively O(1) insertion per element. |
remove(T) |
effectively O(1) | effectively O(1) (one hash lookup and a path copy of the trie). |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements (a hash set of them, then one filter pass). |
replace(T, T) |
effectively O(1) | effectively O(1) (one lookup, one removal and one insertion). |
replaceAll(T, T) |
effectively O(1) | effectively O(1), that of replace(Object,: a set holds an element once. |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements (a hash set of them, then one filter pass). |
union(Set<? extends T>) |
O(m) | O(m) for a set of m elements, each an effectively O(1) insertion; this set or a HashSet argument is returned as is when the other side is empty. |
max() (from Set) |
O(n) | O(n), every element compared once in natural order; on a TreeSet the greatest element in the comparator's order is last(), O(log n). |
min() (from Set) |
O(n) | O(n), every element compared once in natural order; on a TreeSet the least element in the comparator's order is head(), O(log n). |
LinkedHashSet¶
| Method | Cost | Note |
|---|---|---|
flatten(Iterable<? extends Iterable<? extends T>>) |
O(n) | O(n) for n inner elements in total, one effectively O(1) insertion each. |
add(T) |
effectively O(1) | effectively O(1) (one hash lookup, then a hash insertion and an append to the insertion order when the element is new). |
addAll(Iterable<? extends T>) |
O(m) | O(m) for m elements, each an effectively O(1) add(Object); O(1) when this set is empty and elements is a LinkedHashSet, which is returned as is. |
contains(T) |
effectively O(1) | effectively O(1) (one hash lookup). |
diff(Set<? extends T>) |
O(n + m) | O(n + m) for a set of m elements (a hash set of them, then the kept elements copied into a new set). |
intersect(Set<? extends T>) |
O(n + m) | O(n + m) for a set of m elements (a hash set of them, then the kept elements copied into a new set). |
iterator() |
O(1) | O(1) to create; each step is effectively O(1) (one hash lookup), a whole walk O(n). |
asJava() |
O(1) | O(1); contains on the view is effectively O(1), and each step of its iterator, in either order, is effectively O(1). |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n), one effectively O(1) insertion per element. |
remove(T) |
effectively O(1) | effectively O(1) (one hash removal and one marker in the insertion order), amortised: when the markers outnumber the elements, the insertion order is rebuilt in O(n). |
removeAll(Iterable<? extends T>) |
O(m + n) | O(m + n) for m given elements (a hash set of them, then the kept elements copied into a new set). |
replace(T, T) |
effectively O(1) | effectively O(1) amortised, as remove(Object); the new element takes the position of the replaced one. |
replaceAll(T, T) |
effectively O(1) | effectively O(1) amortised, that of replace(Object,: a set holds an element once. |
retainAll(Iterable<? extends T>) |
O(m + n) | O(m + n) for m given elements (a hash set of them, then the kept elements copied into a new set). |
union(Set<? extends T>) |
O(m) | O(m) for a set of m elements, each an effectively O(1) add(Object). |
head() |
effectively O(1) | effectively O(1) (the first element of the insertion order). |
last() |
effectively O(1) | effectively O(1) (the last element of the insertion order). |
init() |
effectively O(1) | effectively O(1) (one element removed from the hash map, the insertion order sliced), plus a walk past the removed elements' markers next to the last element, if any. |
initOption() |
effectively O(1) | effectively O(1) (one init). |
tail() |
effectively O(1) | effectively O(1) (one element removed from the hash map, the insertion order sliced), plus a walk past the removed elements' markers next to the first element, if any. |
tailOption() |
effectively O(1) | effectively O(1) (one tail). |
take(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)) (the smaller of the kept and the removed elements is inserted into or removed from the hash map; the insertion order is sliced). After removals, finding the cut also walks the insertion order from the nearer end past the removed elements' markers. |
takeRight(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)), that of take(int), counted from the other end. |
takeWhile(Predicate<? super T>) |
O(k) | O(k) for a prefix of k elements (one walk), then one take(int). |
takeUntil(Predicate<? super T>) |
O(k) | O(k) for a prefix of k elements (one walk), then one take(int). |
drop(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)), that of take(int). |
dropRight(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)), that of take(int). |
dropWhile(Predicate<? super T>) |
O(k) | O(k) for k dropped elements (one walk), then one drop(int). |
dropUntil(Predicate<? super T>) |
O(k) | O(k) for k dropped elements (one walk), then one drop(int). |
zipWithIndex() |
O(n) | O(n). |
grouped(int) |
O(n) | O(n), that of sliding(int, with a step of size. |
sliding(int) |
O(n * size) | O(n * size), that of sliding(int, with a step of 1. |
sliding(int, int) |
O(n + (n / step) * min(size, n - size)) | O(n + (n / step) * min(size, n - size)): O(n) to drop the removed elements' markers from the insertion order if there are any, then per window that of take(int) on a window of size elements, effectively O(min(size, n - size)). |
slideBy(Function<? super T, ?>) |
O(n) | O(n) walk (plus O(n) to drop the removed elements' markers from the insertion order if there are any), then per run that of take(int) on the run. |
max() (from Set) |
O(n) | O(n), every element compared once in natural order; on a TreeSet the greatest element in the comparator's order is last(), O(log n). |
min() (from Set) |
O(n) | O(n), every element compared once in natural order; on a TreeSet the least element in the comparator's order is head(), O(log n). |
TreeSet¶
| Method | Cost | Note |
|---|---|---|
flatten(Comparator<? super T>, Iterable<? extends Iterable<? extends T>>) |
O(n log n) | O(n log n) comparisons for n inner elements in total. |
flatten(Iterable<? extends Iterable<? extends T>>) |
O(n log n) | O(n log n) comparisons for n inner elements in total. |
add(T) (from SortedSet) |
O(log n) | O(log n) (one lookup, then one insertion in the tree when the element is new). |
addAll(Iterable<? extends T>) (from SortedSet) |
O(m log(n + m)) | O(m log(n + m)) for m elements (one lookup, and one insertion for a new element, each). |
asJava() |
O(1) | O(1); contains, size, first, last, ceiling, floor, higher and lower on the view and on its sub-views are O(log n), an iterator is O(log n) to create and amortized O(1) per step. |
diff(Set<? extends T>) (from SortedSet) |
O((n + m) log n) | O((n + m) log n) for a set of m elements: a split and a join per node of elements when it is a TreeSet with the same comparator, otherwise a hash set of elements and the kept elements built into a new tree. |
contains(T) |
O(log n) | O(log n) comparisons. |
intersect(Set<? extends T>) (from SortedSet) |
O((n + m) log n) | O((n + m) log n) for a set of m elements: a split and a join per node of elements when it is a TreeSet with the same comparator, otherwise a hash set of elements and the kept elements built into a new tree. |
iterator() |
O(log n) | O(log n) to create (the path to the least element); a whole walk is O(n). |
remove(T) (from SortedSet) |
O(log n) | O(log n) (one deletion from the tree). |
removeAll(Iterable<? extends T>) (from SortedSet) |
O(m + n log n) | O(m + n log n) for m given elements (a hash set of them, then the kept elements inserted into a new tree). |
replace(T, T) (from SortedSet) |
O(log n) | O(log n) (one lookup, one deletion and one insertion in the tree). |
replaceAll(T, T) (from SortedSet) |
O(log n) | O(log n), that of replace(Object,: a set holds an element once. |
retainAll(Iterable<? extends T>) (from SortedSet) |
O(m + n log n) | O(m + n log n) for m given elements (a hash set of them, then the kept elements inserted into a new tree). |
union(Set<? extends T>) (from SortedSet) |
O(m log(n + m)) | O(m log(n + m)) for a set of m elements: a split and a join per node of elements when it is a TreeSet with the same comparator, otherwise one lookup and one insertion per element. |
head() (from SortedSet) |
O(log n) | O(log n) (the leftmost path of the tree). |
last() (from SortedSet) |
O(log n) | O(log n) (the rightmost path of the tree). |
init() (from SortedSet) |
O(log n) | O(log n) (one rank split of the tree). |
initOption() (from SortedSet) |
O(log n) | O(log n) (one init). |
tail() (from SortedSet) |
O(log n) | O(log n) (one rank split of the tree). |
tailOption() (from SortedSet) |
O(log n) | O(log n) (one tail). |
take(int) (from SortedSet) |
O(log n) | O(log n) (one rank split of the tree). |
takeRight(int) (from SortedSet) |
O(log n) | O(log n) (one rank split of the tree). |
takeWhile(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for a prefix of k elements (one walk, then one rank split of the tree). |
takeUntil(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for a prefix of k elements (one walk, then one rank split of the tree). |
drop(int) (from SortedSet) |
O(log n) | O(log n) (one rank split of the tree). |
dropRight(int) (from SortedSet) |
O(log n) | O(log n) (one rank split of the tree). |
dropWhile(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for k dropped elements (one walk, then one rank split of the tree). |
dropUntil(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for k dropped elements (one walk, then one rank split of the tree). |
zipWithIndex() (from SortedSet) |
O(n) | O(n). |
grouped(int) (from SortedSet) |
O((n / size) log n) | O((n / size) log n) (one rank slice of the tree per block, sharing its subtrees). |
sliding(int) (from SortedSet) |
O(n log n) | O(n log n) (one rank slice of the tree per window, sharing its subtrees). |
sliding(int, int) (from SortedSet) |
O((n / step) log n) | O((n / step) log n) (one rank slice of the tree per window, sharing its subtrees). |
slideBy(Function<? super T, ?>) (from SortedSet) |
O(n + r log n) | O(n + r log n) for r runs (one walk, then one rank slice of the tree per run). |
max() (from Set) |
O(n) | O(n), every element compared once in natural order; on a TreeSet the greatest element in the comparator's order is last(), O(log n). |
min() (from Set) |
O(n) | O(n), every element compared once in natural order; on a TreeSet the least element in the comparator's order is head(), O(log n). |
HashMap¶
| Method | Cost | Note |
|---|---|---|
containsKey(K) |
effectively O(1) | effectively O(1) (one hash lookup). |
get(K) |
effectively O(1) | effectively O(1) (one hash lookup). |
iterator() |
O(1) | O(1) to create; a whole walk is O(n). |
keySet() |
O(n) | O(n) (the keys are copied into a new HashSet). |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1) (one lookup and one put(Object,). |
put(K, V) |
effectively O(1) | effectively O(1) (a path copy of the trie). |
put(Tuple2<? extends K, ? extends V>) |
effectively O(1) | effectively O(1), that of put(Object,. |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1) (one lookup and one put(Object,). |
remove(K) |
effectively O(1) | effectively O(1) (a path copy of the trie). |
removeAll(BiPredicate<? super K, ? super V>) |
O(n) | O(n) (one filter pass). |
removeAll(Iterable<? extends K>) |
O(m) | O(m) for m given keys, each an effectively O(1) removal. |
replace(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1) (one lookup, one removal and one insertion). |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1), that of replace(Tuple2,: a map holds an entry once. |
replace(K, V, V) |
effectively O(1) | effectively O(1) (one lookup and one insertion). |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) |
O(n) | O(n) (every entry mapped into a new map). |
retainAll(Iterable<? extends Tuple2<K, V>>) |
O(m) | O(m) for m given entries (one lookup, and one insertion into a new map, per entry). |
asJavaMap() |
O(1) | O(1); get and containsKey on the view are effectively O(1). |
values() |
O(n) | O(n). |
contains(T) (from Traversable) |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |
LinkedHashMap¶
| Method | Cost | Note |
|---|---|---|
containsKey(K) |
effectively O(1) | effectively O(1) (one hash lookup). |
get(K) |
effectively O(1) | effectively O(1) (one hash lookup). |
iterator() |
O(1) | O(1) to create; each step is effectively O(1) (one hash lookup per key of the insertion order, skipping the removed keys' markers), a whole walk O(n). |
asJavaMap() |
O(1) | O(1); get and containsKey on the view are effectively O(1), and so is each step of its iterators, in either order. |
keySet() |
O(1) | O(1) (a LinkedHashSet view sharing this map). |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1) (one lookup and one put(Object,). |
put(K, V) |
effectively O(1) | effectively O(1) (one hash lookup and one hash insertion; a new key is appended to the insertion order). |
put(Tuple2<? extends K, ? extends V>) |
effectively O(1) | effectively O(1), that of put(Object,. |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1) (one lookup and one put(Object,). |
remove(K) |
effectively O(1) | effectively O(1) (one hash removal and one marker in the insertion order), amortised: when the markers outnumber the entries, the insertion order is rebuilt in O(n). |
removeAll(BiPredicate<? super K, ? super V>) |
O(n) | O(n) (the kept entries copied into a new map). |
removeAll(Iterable<? extends K>) |
O(m + n) | O(m + n) for m given keys (a hash set of them, a filter of the hash map, then the insertion order rebuilt). |
replace(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1) amortised, as remove(Object); the new entry takes the position of the replaced one. |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1) amortised, that of replace(Tuple2,: a map holds an entry once. |
replace(K, V, V) |
effectively O(1) | effectively O(1) (one lookup and one put of an existing key). |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) |
O(n) | O(n) (every entry put into a new map). |
retainAll(Iterable<? extends Tuple2<K, V>>) |
O(m + n) | O(m + n) for m given entries (a hash set of them, then the kept entries copied into a new map). |
values() |
O(n) | O(n). |
head() |
effectively O(1) | effectively O(1) (the first key of the insertion order, then one hash lookup). |
last() |
effectively O(1) | effectively O(1) (the last key of the insertion order, then one hash lookup). |
init() |
effectively O(1) | effectively O(1) (one key removed from the hash map, the insertion order sliced), plus a walk past the removed keys' markers next to the last entry, if any. |
initOption() |
effectively O(1) | effectively O(1) (one init). |
tail() |
effectively O(1) | effectively O(1) (one key removed from the hash map, the insertion order sliced), plus a walk past the removed keys' markers next to the first entry, if any. |
tailOption() |
effectively O(1) | effectively O(1) (one tail). |
take(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)) (the smaller of the kept and the removed keys is inserted into or removed from the hash map; the insertion order is sliced). After removals, finding the cut also walks the insertion order from the nearer end past the removed keys' markers. |
takeRight(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)), that of take(int), counted from the other end. |
takeWhile(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for a prefix of k entries (one walk), then one take(int). |
takeUntil(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for a prefix of k entries (one walk), then one take(int). |
drop(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)), that of take(int). |
dropRight(int) |
effectively O(min(n, size - n)) | effectively O(min(n, size - n)), that of take(int). |
dropWhile(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for k dropped entries (one walk), then one drop(int). |
dropUntil(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for k dropped entries (one walk), then one drop(int). |
zipWithIndex() |
O(n) | O(n). |
grouped(int) |
O(n) | O(n), that of sliding(int, with a step of size. |
sliding(int) |
O(n * size) | O(n * size), that of sliding(int, with a step of 1. |
sliding(int, int) |
O(n + (n / step) * min(size, n - size)) | O(n + (n / step) * min(size, n - size)): O(n) to drop the removed keys' markers from the insertion order if there are any, then per window that of take(int) on a window of size entries, effectively O(min(size, n - size)). |
slideBy(Function<? super Tuple2<K, V>, ?>) |
O(n) | O(n) walk (plus O(n) to drop the removed keys' markers from the insertion order if there are any), then per run that of take(int) on the run. |
contains(T) (from Traversable) |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |
TreeMap¶
| Method | Cost | Note |
|---|---|---|
containsKey(K) |
O(log n) | O(log n) comparisons. |
get(K) |
O(log n) | O(log n) comparisons. |
iterator() |
O(log n) | O(log n) to create (the path to the least entry); a whole walk is O(n). |
keySet() (from SortedMap) |
O(n log n) | O(n log n) (the keys are built into a new TreeSet). |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) (from SortedMap) |
O(log n) | O(log n) (one lookup and one insertion in the tree). |
put(K, V) (from SortedMap) |
O(log n) | O(log n) (one insertion in the tree). |
put(Tuple2<? extends K, ? extends V>) (from SortedMap) |
O(log n) | O(log n) (one insertion in the tree). |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) (from SortedMap) |
O(log n) | O(log n) (one lookup and one insertion in the tree). |
remove(K) (from SortedMap) |
O(log n) | O(log n) (one lookup and one deletion in the tree). |
removeAll(BiPredicate<? super K, ? super V>) (from SortedMap) |
O(n log n) | O(n log n) (the kept entries inserted into a new tree). |
removeAll(Iterable<? extends K>) (from SortedMap) |
O(m log n) | O(m log n) for m given keys (one lookup, and a deletion when present, per key). |
replace(Tuple2<K, V>, Tuple2<K, V>) (from SortedMap) |
O(log n) | O(log n) (one lookup, one deletion and one insertion in the tree). |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) (from SortedMap) |
O(log n) | O(log n), that of replace(Tuple2,: a map holds an entry once. |
replace(K, V, V) (from SortedMap) |
O(log n) | O(log n) (one lookup and one insertion in the tree). |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) (from SortedMap) |
O(n log n) | O(n log n) (every entry inserted into a new tree). |
retainAll(Iterable<? extends Tuple2<K, V>>) (from SortedMap) |
O(m log n) | O(m log n) for m given entries (one lookup per entry, the present ones inserted into a new tree). |
values() |
O(n) | O(n). |
head() (from SortedMap) |
O(log n) | O(log n) (the leftmost path of the tree). |
last() (from SortedMap) |
O(log n) | O(log n) (the rightmost path of the tree). |
init() (from SortedMap) |
O(log n) | O(log n) (one rank split of the tree). |
initOption() (from SortedMap) |
O(log n) | O(log n) (one init). |
tail() (from SortedMap) |
O(log n) | O(log n) (one rank split of the tree). |
tailOption() (from SortedMap) |
O(log n) | O(log n) (one tail). |
take(int) (from SortedMap) |
O(log n) | O(log n) (one rank split of the tree). |
takeRight(int) (from SortedMap) |
O(log n) | O(log n) (one rank split of the tree). |
takeWhile(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for a prefix of k entries (one walk, then one rank split of the tree). |
takeUntil(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for a prefix of k entries (one walk, then one rank split of the tree). |
drop(int) (from SortedMap) |
O(log n) | O(log n) (one rank split of the tree). |
dropRight(int) (from SortedMap) |
O(log n) | O(log n) (one rank split of the tree). |
dropWhile(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for k dropped entries (one walk, then one rank split of the tree). |
dropUntil(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for k dropped entries (one walk, then one rank split of the tree). |
zipWithIndex() (from SortedMap) |
O(n) | O(n). |
grouped(int) (from SortedMap) |
O((n / size) log n) | O((n / size) log n) (one rank slice of the tree per block, sharing its subtrees). |
sliding(int) (from SortedMap) |
O(n log n) | O(n log n) (one rank slice of the tree per window, sharing its subtrees). |
sliding(int, int) (from SortedMap) |
O((n / step) log n) | O((n / step) log n) (one rank slice of the tree per window, sharing its subtrees). |
slideBy(Function<? super Tuple2<K, V>, ?>) (from SortedMap) |
O(n + r log n) | O(n + r log n) for r runs (one walk, then one rank slice of the tree per run). |
asJavaMap() |
O(1) | O(1); get, containsKey, size, firstKey, lastKey and the ceiling, floor, higher and lower lookups on the view and on its sub-views are O(log n), an iterator is O(log n) to create and amortized O(1) per step. |
contains(T) (from Traversable) |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |