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
tlum...@u.washington.edu University of Washington, Seattle
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
