Anatomy of divide and conquer

Report a typo

Please look again at the pseudocode from our theory. It calculates the sum of an array using the divide and conquer paradigm.

function f(array, left, right):
    if left == right then:
        return 0    
    if left == right-1 then:
        return array[left]
    middle = int((left + right) / 2)
    left = f(array, left, middle)
    right = f(array, middle, right)
    return left + right

Here int()int() function returns the largest integer less than the given number, for example, int(4.5)int(4.5) will return 4.

Can you please distinguish the base cases, the divide and conquer, and the combining portion of the code?

Match the items from left and right columns
Base cases
Divide and conquer
Combining
Line 9 of code
Lines 2 to 5 of code
Lines 6-8 of code
___

Create a free account to access the full topic