Important - demonstration

[Lordofnazgul]

hello! i need your help about this exercise:

Let { xi } i=0, .. .. .. , 2n 2n+1 distinct points on the real line



2n
we define ∑ 0 = ∑ | x(0) - x(i)|
i=0



2n
∑ 1 = ∑ | x(1) - x(i)|
i=0


prove that there is a linear algorythm that says: ∑ = {∑ | i:0,.. .. .. ,2n}
min i


i solve this exercise (i found that the element that minimizes this function is the element nearest to the average of the numbers that i gave in input, and the compexity is O(6n + 2) in the worst case. Do you know how to demonstrate this algorythm???


p.s. when i write for example x(0), x(1), 0 and 1 are the subscripts of x.
thank you!