Writing a Recurrence Equation

Question

I am confused on where the 2nd term [T(n) = 2T(n/2) + THETA(n)] is derived from when writing the recurrence equation for Merger Sort.

From the Coursera class, it was stated that the 2nd term is due to what occurs outside of the recursive calls. So my guess is because it is due to the 2 For Loops, each would go up to n/2, so the total would be counting to n:

    function mergesort(m)
    var list left, right
    if length(m) ≤ 1
        return m
    else
        middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        left = mergesort(left)
        right = mergesort(right)
        result = merge(left, right)
        return result

Any help would be appreciated. Thanks

Answer 1

Yes, that's right. There's linear work done to iterate across the elements of the input list, distributing each element into either the left or right subarray. That accounts for the Θ(n) term in the recurrence.

Hope this helps!