Difference between revisions of "TADM2E 4.6"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
Line 2: Line 2:
  
 
One more approach to solve the above problem
 
One more approach to solve the above problem
<pre>
+
<pre>
 
1. Sort S1; (n log n)
 
1. Sort S1; (n log n)
 
2. Sort S2; (n log n)
 
2. Sort S2; (n log n)
 
3. beg := S1[0]
 
3. beg := S1[0]
 
   end := S2[m-1]
 
   end := S2[m-1]
4. while (beg &lt; n &amp;&amp; end &gt;=0 ) O(n)
+
4. while (beg < n && end >=0 ) O(n)
       if S1[beg] + S2[end] &gt; sum then end--
+
       if S1[beg] + S2[end] > sum then end--
       else if S1[beg] + S2[end] &lt; sum  beg++
+
       else if S1[beg] + S2[end] < sum  beg++
 
       else return (beg, end)
 
       else return (beg, end)
 
   End Loop
 
   End Loop
  
 
Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)
 
Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)
&lt;/pre&gt;
+
</pre>
 
--[[User:Max|Max]] 07:04, 25 June 2010 (EDT)
 
--[[User:Max|Max]] 07:04, 25 June 2010 (EDT)
  
 
A third approach
 
A third approach
&lt;pre&gt;
+
<pre>
 
1. Sort S1; O(n log n)
 
1. Sort S1; O(n log n)
 
2. for i=0 to n-1
 
2. for i=0 to n-1
Line 25: Line 25:
 
         return (val, S2[i])
 
         return (val, S2[i])
 
   End Loop
 
   End Loop
&lt;/pre&gt;
+
</pre>
  
 
Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)
 
Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)

Revision as of 18:23, 11 September 2014

subtract n from the first set, sort both sets in O(nlogn). find the first equal under n

One more approach to solve the above problem

1. Sort S1; (n log n)
2. Sort S2; (n log n)
3. beg := S1[0]
   end := S2[m-1]
4. while (beg < n && end >=0 ) O(n)
      if S1[beg] + S2[end] > sum then end--
      else if S1[beg] + S2[end] < sum  beg++
      else return (beg, end)
   End Loop

Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)

--Max 07:04, 25 June 2010 (EDT)

A third approach

1. Sort S1; O(n log n)
2. for i=0 to n-1
      val := x - S2[i]
      if binary_search(S1, val) O(log n)
         return (val, S2[i])
   End Loop

Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)