performance - Given two buckets each containing an identical set of balls, each ball with two colored numbers, does a certain matching algorithm scale as N^2? -

performance - Given two buckets each containing an identical set of balls, each ball with two colored numbers, does a certain matching algorithm scale as N^2? -

for client, have scaling problem have boiled downwards next fundamental combinatorics problem.

suppose there bucket containing n balls, each ball random reddish number , random bluish number written on it. (assume numbers positive integers.)

suppose there sec bucket identical set of balls (i.e., has n balls , balls correspond balls in first bucket, in terms of numbers written on balls.)

the question i'd reply client efficiently possible big n in computer programme following:

consider every possible pairing of balls between 2 buckets (i.e., 1 ball first bucket , 1 ball sec bucket). how many such pairs satisfy status product of 2 reddish numbers in pair same product of 2 bluish numbers in pair?

the question here stackoverflow is: efficient possible algorithm solve problem o(n^2)? think so, cannot prove it.

thanks!

nope. have o(n) solution, involving hashtable on (reduced) ratio of red_value/blue_value 1 of buckets. filling hashtable o(n). matching blue_value/red_value other bucket against table o(n), since each lookup o(1).

it's hashtable, not hashset, because there can multiple balls same ratio.

one can utilize trie o(1) lookups.

performance math combinations scaling combinatorics