Difference between revisions of "Talk:TADM2E 4.6"

From Algorithm Wiki
Jump to: navigation, search
 
Line 3: Line 3:
 
* For each value in S2 look for a hash hit on x-S2[i].
 
* For each value in S2 look for a hash hit on x-S2[i].
 
Isn't that an O(n) solution?
 
Isn't that an O(n) solution?
 +
 
According to the formal definition, an O(n) solution is also an O(n log n) solution, is it not?
 
According to the formal definition, an O(n) solution is also an O(n log n) solution, is it not?

Latest revision as of 19:16, 19 May 2017

What about this approach?

  • Create a hash entry for every value from S1[i].
  • For each value in S2 look for a hash hit on x-S2[i].

Isn't that an O(n) solution?

According to the formal definition, an O(n) solution is also an O(n log n) solution, is it not?