Hi, I’d like to suggest adding time complexity in...

# library-development

[mika]

Hi,

I’d like to suggest adding time complexity information for functions in Kotlin, especially in the Standard Library. Swift provides a great example of this—functions like Array.contains(_:) come with documented complexity, which I find very useful. I really miss having something similar in Kotlin.

Here’s why I believe it would be valuable:
1. It enhances the development experience.
2. It promotes better, more efficient code.
3. It serves as a helpful form of documentation.
4. It centralizes the work, saving every developer from having to research complexities individually.

One possible approach could be to automate the calculation of time complexity empirically, using performance measurements across different n values and object types (based on platform and common use cases).

Please let me know what you think—I’d be happy to assist with this.

Best regards,
Mika

[Joffrey]

Collection operations might have different performance profiles depending on the implementation. Something like contains for a collection vastly depends on whether it's an ArrayList, a HashSet, a TreeSet, etc.

[mika]

Thank you for your feedback—I agree for some functions it is not necessary or possible (e.g. functions which take lambdas). However, I believe that documenting time complexity for commonly used cases, like standard collections, could still be very beneficial.
Empirical testing could offer a way to automate this process and make fine tuning code easier for everyone.

[Joffrey]

I'm not sure how you mean. Any polymorphic method would require enumerating all common subtypes, and same goes for every extension that ends up calling polymorphic functions. Do you mean we should list all these subtypes and associated complexity in the doc of these functions?

[Joffrey]

That said, I believe we should document complexity on the implementation types themselves. In java, this is what is done, but the Kotlin docs don't reflect that. See the difference:
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-hash-map/

[mika]

To your first point. I do not believe we should do it for the polymorphic functions, if the complexity is ambiguous. Rather I would do it for the concrete instance. e.g HashSet.contains (add it here: https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-hash-set/) and when you hover over this in your IDE.

[Joffrey]

We could, but most well written code wouldn't expose the runtime type as the static type of the variable, instead variables should be of the type of the interface. So the specific implementation's doc never appears in practice when you hover on usages.

[Joffrey]

The decision about the complexity happens at the instantiation time, so when you choose the constructor of a particular implementation. And over there it could definitely be improved