Difference between revisions of "TADM2E 4.2"

Latest revision as of 23:57, 20 November 2019

(a) Iterate over the array once, keeping track of the max and min values respectively for x and y. This will have $$ 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 (c), after sorting.

@@ 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) Iterate over the array once, keeping track of the max and min values respectively for x and y. This will have <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 nLog(n) method. Then scan through the sorted array to find the smallest gap, thus the desired pair.
+(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 (c), after sorting.