Important - demonstration

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!

Your phrasing and formulas are not very clear.
I'm not sure what the linear algorithm should do. The formula is strange.
Please describe it also in words or attach a bitmap of the exact equations.

Regards,
Zachm

Quote:

---

Originally Posted by Zachm

Your phrasing and formulas are not very clear.
I'm not sure what the linear algorithm should do. The formula is strange.
Please describe it also in words or attach a bitmap of the exact equations.

Regards,
Zachm

---

here it is:

http://img98.imageshack.us/img98/6299/algorythm.jpg


sorry for bad posting before. The Algorythm i created finds the average of the numbers, and then finds the element that is the nearest to the average. the complexity is O(6n + 2). but i don't know how to demonstrate that my algortyhm works. thank you