CODEWITHSUNDEEP
algorithmlistocamlcomplexity-theory
SoftTimur
SoftTimur

Reputation: 5510

Complexity of List.mem

I have an algorithm manipulating a list, and I would like to express its complexity.

In the algorithm, I have List.mem a l inside a loop, and I am not sure how to consider the complexity of List.mem, must it be O(List.length(l)), or Ocaml can do something magic inside to be better than O(List.length(l))?

Upvotes: 2

Views: 899

Answers (2)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66803

There's no magic, here's the implementation (OCaml 3.12.0):

let rec mem x = function
    [] -> false
  | a::l -> compare a x = 0 || mem x l

If you have an OCaml source distribution, this is in the file named stdlib/list.ml (line 135).

Upvotes: 5

univerio
univerio

Reputation: 20518

No, with a linked list, the best you can theoretically do to check for membership is O(n). You can improve on that by sacrificing space, i.e. using a hashtable instead, or having a hashtable alongside this list if you care about order.

Upvotes: 1

Related Questions