Divide and conquer algorith does not work

Question

I am trying to resolve the average of numbers using a "divide and conquer" algorithm but the program that i have written only works when the number of elements is power of two (2,4,8,etc).

The code is written in python and it is as follows

def averageDyC(ini, end, notes):
    if (ini == end):
        return notes[ini]

    mid = int((ini + end) / 2)

    x = averageDyC(ini, mid, notes)
    y = averageDyC(mid + 1, end, notes)
    
    return float((x + y) / 2)
    
notes = [1, 4, 7, 8, 9, 2, 4]
average = averageDyC(0, len(notas) - 1, notes)

This code displays 3,75 but the correct average is 3,5

How can I chage this code to allow number of elements different of power of 2?

Mathematically, this aproch is wrong, why don't you use `sum(notes)/len(notes)`. — Roshin Raphel, Jul 17 '20 at 14:49
Have you tried to use a debugger to check that your program does with it is supposed to do? — rveerd, Jul 17 '20 at 14:51
As has been pointed out in other answers, you can fix the logic of your algorithm by weighting the averages: replacing the line `return float((x + y) / 2)` with `return float((x*(mid-ini+1) + y*(end-mid)) / (end-ini+1))`. However, this performs a lot of intermediate divisions and remultiplications, which is somewhat inefficient, and might result in rounding and approximations. As Roshin Raphel pointed out, your whole algorithm can be replaced with the simple line `sum(notes)/len(notes)`, which performs exactly one division. — Stef, Jul 20 '20 at 13:21
@Stef, your comment is amazing. I have changed my code with the proposal line weighting the averages and the result is right without depending the number of elements. — Iván, Jul 21 '20 at 14:43

score 4 · Answer 1 · edited Jul 17 '20 at 14:53

I don't actually think this technique can work for finding the average of a list.

Let's look at a list of three numbers: [1,2,3]

Clearly, the average is 2.

However, if we divide the list in two, we get [1,2] and [3]. Their respective averages are 1.5 and 3.

If we then add those two together then divide the result by two, we get 2.25.

That's because 1.5 is the average of two numbers, and 3 is the average of one number, so we should really be weighting the 1.5 with 2 and the 3 with 1.

So the correct sum would be (2(1.5) + 1(3)) / 3.

This same problem will occur whenever you try to divide an odd list into two halves and then give the two averages equal weighting.

For that reason, I don't think you can use this approach other than where you have a power of two length list.

EDIT: It's also worth noting that there are many good ways to get the average of a list (see this previous question). I haven't focussed on these as I believe your question is mainly asking about the specific algorithm you've used, not actually finding the average.

Divide and conquer algorith does not work

1 Answers1