What is the complexity of List.nth in OCaml? Can we find the nth element in OCaml in O(1)?

Question

I found the manual of OCaml List module did not say how the List.nth does. Does it cost O(1) or O(n) like some plain recursive implementation. If List.nth is O(n), can we write a function to find the nth element in O(1) time in OCaml?

Answer 1

1) If we look at the implementation of List.nth in https://github.com/janestreet/core_kernel/blob/master/lib/core_list.ml (Lines 193 to 200) we see that it calls a tail recursive function that uses the cons (::) operator to repeatedly extract the head element. Therefore, we can be sure that it is indeed O(n).

2) If the lists that we were working with were big we could convert them into arrays using to_array ( val to_array : 'a t -> 'a array ) and use these arrays for more efficient lookups. But this approach works only in very simple cases where the we build the entire list first and then perform the lookups. I'd like to think of these array as indexes for the lists; and like in relational db implementations we would have to update the indexes when the base data changes.

Answer 2

It is O(n).

And as long as it is a standard linked-list, you can't find the nth element in O(1) in any language.

Answer 3

Standard lists are "singly-linked", so it will always be O(n).