0

Find sum of all even number in an array. A recursive program to get the sum. What is the time complexity of this program and how to do I analyze it?

def sumEven(arr):
    if len(arr) == 0:
        return 0
    if len(arr) == 1:
        if arr[0]%2 == 0:
            return arr[0]
        else:
            return 0
    else:
        mp = len(arr)//2
        return sumEven(arr[0:mp]) + sumEven(arr[mp:])
Aravind
  • 550
  • 7
  • 17
  • 1
    The code sums the even numbers in the array. A O(log n) algorithm can only look at O(log n) entries in the array. – Paul Hankin Feb 09 '17 at 03:45
  • Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Paul Hankin Feb 09 '17 at 03:46

1 Answers1

2

It's still O(n) (n/2 if you want to be more precise). You're splitting the work in half at each step, but it has to be recombined as you go up the chain. You cannot add all the even values without performing #even values - 1 addition operations, minimum. This just improves the odds that any given addition is with roughly equal sized operands, where looping directly would have one accumulator operand continually growing as the source operands stay the same size.

Ignoring the evenness element, think of summing all the numbers in the array this way. If you had eight elements, you'd add the even elements to the odd (four operations, leaving four elements), then add the even results to the odd results (two operations, leaving two elements), then add those two remaining values together (one operation, leaving the answer). You performed 4 + 2 + 1 == 7 operations to add 8 values. You'd have done the same number with just:

 elems = [1,2,3,4,5,6,7,8]

 accumulator = elems[0]
 # Loop runs seven times, for all but first element, so seven additions performed
 for operand in elems[1:]:  # Ignore the slice cost here; avoidable, but irrelevant
     accumulator += operand
ShadowRanger
  • 143,180
  • 12
  • 188
  • 271