R help - Sep 2009 - What is the time complexity of 'match()'?

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?

Regards,
Peng

try running it on a grid within "system.time()"
And the answer will be revealed.

Tal





On Thu, Sep 17, 2009 at 3:15 PM, Peng Yu <pengyu.ut@gmail.com> 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?
>
> Regards,
> Peng
>
> ______________________________________________
> 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.
>


-- 
----------------------------------------------


My contact information:
Tal Galili
Phone number: 972-50-3373767
FaceBook: Tal Galili
My Blogs:
http://www.r-statistics.com/
http://www.talgalili.com
http://www.biostatistics.co.il

	[[alternative HTML version deleted]]

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