CODEWITHSUNDEEP
javaarraysperformancecollectionstime-complexity
Adilli Adil
Adilli Adil

Reputation: 1261

What is the time complexity of Collection.toArray()?

What is the time complexity of the method Collection.toArray()? is it O(n), if yes than what benefits does it offer over looping and individually assigning the values in the list to an array( beside nice look and some extra effort of course).

Upvotes: 5

Views: 10459

Answers (2)

Tregoreg
Tregoreg

Reputation: 22166

Because toArray() method is abstract, speaking about its time complexity in general makes no sense.

However, for native implementations, the complexity is indeed O(n). It is noteworthy that Collection is a subinterface of Iterable. It would we quite absurd to implement an Iterable which cannot be efficiently iterated over.

The fact that the implementation of toArray() is kept open, leaves space for optimizations. There may be approaches faster than building the array using simple iteration (array copying, running in multiple threads...). However, the default implementaion in AbstractCollection uses the exact approach that you mention in your question.

Upvotes: 4

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726499

A call of toArray() on any collection walks the entire collection. For all collections from java.util this means O(n) timing. Of course implementations that are slower than O(n) can be constructed as well, but O(n) provides a lower bound for the timing, because you have to traverse the entire collection.

You call toArray() when you need to call an API that specifically asks for an array, or in situations when you want to make a copy of your collection for any reason. In general, you do not want to overuse toArray(), because it allocates additional memory sufficient to fit all elements of your collection.

Upvotes: 1

Related Questions