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 charge particles at regular spacing along a straight line. Thus we can model their structure as consistin of the points $1,2, 3, ,n)on the real line; and at each of these points j, they have a particle wit charge qj. (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 Cqg G- i)2 G - 02 i j then Add Endif Endfor Output F Endfor It's not hard to analyze the running time of this program: each invocation of the inner loop, over takes O(n) time, and this inner loop is invoked O(n) times total, so the overall running time is o(n2) 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 Fi 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 Fj in O(n log n) time 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 charge particles at regular spacing along a straight line. Thus we can model their structure as consistin of the points $1,2, 3, ,n)on the real line; and at each of these points j, they have a particle wit charge qj. (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 Cqg G- i)2 G - 02 i j then Add Endif Endfor Output F Endfor It's not hard to analyze the running time of this program: each invocation of the inner loop, over takes O(n) time, and this inner loop is invoked O(n) times total, so the overall running time is o(n2) 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 Fi 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 Fj in O(n log n) time