[Haskell-beginners] vector indexing time

Heinrich Apfelmus apfelmus at quantentunnel.de
Fri Aug 3 13:50:11 CEST 2012

Ivan Vyalov wrote:
> Hi everyone!
> I have a question about time complexity of vector indexing.
> Obviously, it should be constant, but if I do the following naive
> tests it looks linear. What do I do wrong?

Creating the vector still takes time proportional to the length of the 
vector. In fact, it appears that in your example, the  vector  packages 
optimizes the creation time to create only up to the element that you 
actually demand.

The linear time you're seeing is not the result of an inefficiency of 
vector indexing, but the result of an efficiency in vector creation.

Best regards,
Heinrich Apfelmus


More information about the Beginners mailing list