I have this confusion related to solving this problem

You’ve been working with some physicists who need to study, as part of their experimental design, the interactions among large numbers of very small charged particles. Basically, their setup works as follows. They have an inert lattice structure, and they use this for placing charged particles at regular spacing along a straight line. Thus we can model their structure as consisting of the points $ \{1, 2, 3, \cdots , n\}$ on the real line; and at each of these points $j$, they have a particle with charge $q_j$. (Each charge can be either positive or negative.)

They want to study the total force on each particle, by measuring it and then comparing it to a computational prediction. This computational part is where they need your help. The total net force on particle $j$, by Coulomb’s Law, is equal to

$F_j = \sum_{i<j}\frac{Cq_iq_j}{(j-i)^2} - \sum_{i>j}\frac{Cq_iq_j}{(j-i)^2}$

They’ve written the following simple program to compute $F_j$ for all $j$:

For j = 1, 2,...,n 
   Initialize Fj to 0 
   For i = 1, 2, ..., n
     If i < j then
       Add Cqiqj/(j-i)^2 to Fj
     Elseif i > j then
       Add −Cqiqj/(j−i)^2 to Fj
   Output Fj 

It’s not hard to analyze the running time of this program: each invocation of the inner loop, over i, takes $O(n)$ time, and this inner loop is invoked $O(n)$ times total, so the overall running time is $O(n^2)$.

The trouble is, for the large values of $n$ they’re working with, the program takes several minutes to run. On the other hand, their experimental setup is optimized so that they can throw down $n$ particles, perform the measurements, and be ready to handle n more particles within a few seconds. So they’d really like it if there were a way to compute all the forces $F_j$ much more quickly, so as to keep up with the rate of the experiment.

Help them out by designing an algorithm that computes all the forces $F_j$ in $O(n \log n)$ time.

I am sure that this problem is solved by convolution which takes time $O(n \log n)$. However, I am not being able to proceed and see how it's converted to a problem related to convolution. Any suggestions?

  • 1
    $\begingroup$ if this is a class exercise [apparently] it would be more polite to say so & give more details eg specific class, book, etc. $\endgroup$ – vzn Jun 10 '13 at 3:04
  • $\begingroup$ This problem appears in J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley (2006), Divide and Conquer chapter as one of the excercises. $\endgroup$ – 89f3a1c Jul 22 '19 at 15:36

Hint: Consider the two sequences $q_1,\ldots,q_n$ and $\ldots,-1/9,-1/4,-1,0,1,1/4,1/9,\ldots$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.