Difference between revisions of "TADM2E 4.2"
From Algorithm Wiki
(Recovering wiki) |
Letientai299 (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | (a) Check the first 3 integers in the array, and get rid of the middle one. Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in O(n) worst-case time. | + | (a) Check the first 3 integers in the array, and get rid of the middle one. Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in <math>O(n)</math> worst-case time. |
| − | (b) The answer is straight forward: S[1] and S[n], since they are the two extreme values. | + | (b) The answer is straight forward: <math>S[1]</math> and <math>S[n],</math> since they are the two extreme values. |
| − | (c) Sort the array with any | + | (c) Sort the array with any <math>n\log(n)</math> method. Then scan through the sorted array to find the smallest gap, thus the desired pair. |
(d) Same as above. | (d) Same as above. | ||
Revision as of 16:50, 11 October 2016
(a) Check the first 3 integers in the array, and get rid of the middle one. Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in $ O(n) $ worst-case time.
(b) The answer is straight forward: $ S[1] $ and $ S[n], $ since they are the two extreme values.
(c) Sort the array with any $ n\log(n) $ method. Then scan through the sorted array to find the smallest gap, thus the desired pair.
(d) Same as above.
