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

Thomas Lumley tlumley at u.washington.edu
Thu Sep 17 15:46:11 CEST 2009


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




More information about the R-help mailing list