working with Physicists that hav an inert lattice structure, and they use this for placing charged particles at regual spacing along a straight line. Thus we can model their structure as consisting of the points 1,2,3,...,n on the real line; and at each of these points j, they have a particle with charge      \(q_i\)   (each charge can be either positive or negative). The total net force on particle j, by Coulombs Law is      i} \frac{C q_iq_j}{(j-i)^2} - \sum_{j< i} \frac{C q_iq_j}{(j-i)^2}" style="margin: 5px 0px 0px; padding: 0px; border: 0px; font-family: inherit; font-size: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; vertical-align: baseline; display: block; width: 665px;">\(F_j= \sum_{j>i} \frac{C q_iq_j}{(j-i)^2} - \sum_{j< i} \frac{C q_iq_j}{(j-i)^2}\)   .

They have written a simple program to compute Fj for all j:

For j=1,2,.....,n

      Initialize Fj to 0

For i=1,2,....,n

      if i

        Add (C qi qj)/(j-i)^2 to Fj

     else  if i>j then

         Add -(C qi qj)?(j-1)^2 to Fj

     Endif

Endfor

Output Fj

Endfor

This runs on O(n^2) time. How can we improve the algorithm to get a run time of O( n log n)?

Would you implement the divide and conquer method and use merge sort? if you do how would you do that?

Please help me figure this out, I am totally new to this and just don't grasp the concepts 100% yet.