CODEWITHSUNDEEP
ocamlcomplexity-theorylookup
RUser4512
RUser4512

Reputation: 1074

OCaml complexity of List.assoc

In the List module of OCaml, how is : val assoc : 'a -> ('a * 'b) list -> 'b implemented and (therefore) what is the complexity of this operation ? Is there a hashtbl hidden behind the scenes ?

Upvotes: 2

Views: 877

Answers (1)

glennsl
glennsl

Reputation: 29106

The code is available online here: https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml#L180-L182

let rec assoc x = function
    [] -> raise Not_found
  | (a,b)::l -> if compare a x = 0 then b else assoc x l

As you can see it's implemented as a linear search over the list.

Upvotes: 7

Related Questions