[R] What is the time complexity of 'match()'?

[Thomas Lumley]

On Thu, 17 Sep 2009, Peng Yu wrote:

> Hi,
>
> Suppose 'x' is a vector of length n and 'y' is a vector of length m, I
> am wondering what the time complexity of 'match(x,y)' is. Is it n
> times m?

match() hashes the second argument then does hash lookups for the first argument (the source is in src/main/unique.c), so its time complexity will be close to m+n.

Even just sorting the second argument and doing binary search would allow (m+n)log(m) complexity -- it really would take a brute force and ignorance approach to give mn time complexity, and match() is sometimes used for quite large m and n.

      -thomas


Thomas Lumley			Assoc. Professor, Biostatistics
tlumley at u.washington.edu	University of Washington, Seattle