[Docs] Adding runtime complexity to relevant functions

[hoxha-saber]

Where is the problem?

https://docs.modular.com/mojo/stdlib/utils/vector.html#setitem__-2

What can we do better?

Throughout the documentation, there are several functions that are used to manipulate data structures. I think it would be helpful as a developer to know runtime complexity of using these functions. For example, in the documentation for unordered_map at cppreference there is a short description of the asymptotic complexity of the insert method.

Complexity
1-6) Average case: O(1), worst case O(size())
7,8) Average case: O(N), where N is the number of elements to insert. Worst case: O(N*size()+N)
9,10) Average case: O(1), worst case O(size())```

Whereas for std::map::insert we have something like

Complexity
1-3) Logarithmic in the size of the container, O(log(size())).
4-6) Amortized constant if the insertion happens in the position just after (until C++11)before (since C++11) pos, logarithmic in the size of the container otherwise.
7,8) O(N·log(size() + N)), where N is the number of elements to insert.
9) Logarithmic in the size of the container, O(log(size())).
10) Amortized constant if the insertion happens in the position just before pos, logarithmic in the size of the container otherwise.

As Mojo evolves and new data structures are added it would be helpful as a developer to get a basic idea of the runtimes for different functions/data structures.

Anything else?

I put a link to __setitem__ function of DynamicVector but it really applies to any/all non-trivial functions.

[scottamain]

Thanks for this suggestion! This is definitely something to consider, but Mojo is still very young and changing quickly, so I think we should revisit this when the language and library is more mature. I believe writing this sort of documentation now will be a maintenance problem, and there are a lot of other pressing demands.