Hi, I'm trying to create an algorithm, and I'm stuck at one point. Say I have a set of N items, all have their points, and ordered by their ranks.

For example:

list1 = { // N = 4

1: (item1, points: 100, rank:1),

2: (item2, points:55, rank:2),

3: (item3, points:55, rank:2),

4: (item4, points:45, rank:3) }

and so on.

list2 is another list of these 4 (N) items, but with different points, thus different ranks. I'm trying to do a comparison for these two lists, like the sum of the differences of item ranks in two lists.For example:

list2 = {

1: (item4, points: 10, rank:1),

2: (item3, points:9, rank:2),

3: (item2, points:8, rank:3),

4: (item1, points:7, rank:4) }

in this case the sum of differences S = (item1 rank difference + item2 " " + ....) S= 3 + 1 + 0 + 2 = 6

in order to compare it with the worst case, I need this sum's worst value for different N's.

so, what is the maximum value of S in terms of N? S_max (N) =?

Thanks for any help.

- Notes:

My solution was assuming the two lists were reversely-ordered for the worst-case sum. Which yielded this solution:

if (N is even)

Smax=(N^2)/4 ;

else (N is odd)

Smax =((N^2)-1)/4 ;

But this solution seems to be wrong, since sometimes it yields negativepercent similarity, which means the current sum (S) is greater than Smax.