What is the time-complexity of the groupingBy{ it }.eachCount() operation?

fun main() {
     val a = listOf(1, 1, 3, 3, 3, 5, 8, 8)
     val counter = a.groupingBy { it }.eachCount()
     println(counter)
}

Here is the source code for both functions:

public actual fun <T, K> Grouping<T, K>.eachCount(): Map<K, Int> =
    foldTo(destination = mutableMapOf(),
           initialValueSelector = { _, _ -> kotlin.jvm.internal.Ref.IntRef() },
           operation = { _, acc, _ -> acc.apply { element  = 1 } })
    .mapValuesInPlace { it.value.element }

public inline fun <T, K> Array<out T>.groupingBy(crossinline keySelector: (T) -> K): Grouping<T, K> {
    return object : Grouping<T, K> {
        override fun sourceIterator(): Iterator<T> = [email protected]()
        override fun keyOf(element: T): K = keySelector(element)
    }
}

CodePudding user response：

It is O(N) where N is the number of items in the list.

The algorithm iterates over the source list, for each item it acquires its key, searches for the counter in the map and increments it. Map access is constant (not counting sporadic re-hashing), so the time increases only due to iteration over the source iterable.

Disclaimer: note that the time complexity of a hash map isn't that easy to estimate due to potential collisions and re-hashing. For example, if we add N different items into a hash map, then we need log(N) re-hashing operations and the biggest one (the last one) is N. So we could argue the whole operation is actually O(N * log(N)). However, generally speaking put() is considered to have amortized time of almost O(1).