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!

[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

[Lordofnazgul]

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