Difference between revisions of "Talk:TADM2E 4.6"
From Algorithm Wiki
Brownslink (talk | contribs) (O(n) Solution) |
|||
| (One intermediate revision by the same user not shown) | |||
| 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? | ||
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?
