CODEWITHSUNDEEP
pythondivide-and-conquer
Roosh
Roosh

Reputation: 37

Divide and Conquer array summation or Loop based array Summation?

I tried to sum an array using this two Algorithms:

Here is the code:

# Summation divide and conquer
def summation(array,left,right):
   if left == right:
       return array[left]
   else:
       if left == right-1:
           return array[left] + array[right]
       else:
           mid  = left + (right-left)//2
           left_hand = summation(array,left,mid)
           right_hand = summation(array,mid+1,right)
           return left_hand + right_hand

And..

# Loop summation
def summation_normal(array):
   sums = 0
   for i in range(len(array)):
       sums += array[i]
   return sums

Both of the above algorithms are working correctly and asymptotically both are O(n).

But I am not able to Identify whether which one of them is faster. Please help

Upvotes: 0

Views: 1068

Answers (2)

trincot
trincot

Reputation: 350310

The number of additions performed on array values is (almost!) the same in both algorithms, but the recursive one has more overhead, so it will run slightly slower.

You can visualise the recursive algorithm going through a binary tree, taking the values of two child nodes and summing them into their parent node. So the number of additions (of array values) corresponds to the number of inner nodes of that tree.

Now look at a short array of 2 elements (with indexes 0 and 1):

       +
      / \
     0   1

The plus represents the only addition that happens in the recursive algorithm. Now visualise that one element is added to the array. This means one of the leaf-nodes becomes a parent of two leaf nodes (one leaf node is added). For example:

       +
      / \
     +   2
    / \
   0   1

So now one more addition needs to be performed: there is one more inner node. You can easily see that adding another array element in this structure increases the number of inner nodes with 1. So there will be one more addition.

Again, in the tree representation, the leaf nodes represent the array values and the inner nodes represent the intermediate sums that are made.

The number of leaves in a binary tree is always one more than the number of inner nodes. And so the number of additions involving array values is n-1. This is one less than the iterative solution, because there the first (and extra) addition is 0 + array[0]. You could improve that by starting with array[0] and start your loop at index 1. If you do that, both algorithms will perform n-1 additions involving array values.

Obviously the recursive algorithm has more "housekeeping" to do: calculating the middle index, using the stack for passing arguments, ...etc, so it will be a bit slower, but not with a different time complexity.

Upvotes: 1

quest
quest

Reputation: 3926

I will do something like this:

a = np.random.randint(0, 1000, 10000)
%timeit summation(a, 0, len(a)-1)
3.59 ms ± 81 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Output:

%timeit summation_normal(a)
1.29 ms ± 7.45 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Please do keep in mind these timings depend a lot on the activities going on in your processor and several other factors.

Clearly summation_normal is the winner here.

Upvotes: 0

Related Questions