Hashset toList() time complexity in kotlin, is it constant or not?

Question

I'd imagine it could be O(1) but can't find any info on it online.

Answer 1

Here's the relevant implementation:

public fun <T> Iterable<T>.toList(): List<T> {
    if (this is Collection) {
        return when (size) {
            0 -> emptyList()
            1 -> listOf(if (this is List) get(0) else iterator().next())
            else -> this.toMutableList()
        }
    }
    return this.toMutableList().optimizeReadOnlyList()
}

It looks like it boils down to the usage of the ArrayList(elements: Collection<E>) constructor which is used in toMutableList. An ArrayList is backed by an array which results in O(n) time when creating the array. Please keep in mind that this eventually depends on what list implementation is used. Right now it is ArrayList.