There are three unnumbered cases inside this leaf.
For the nine-child recurrence, a recursion tree has subproblems of size about . There are constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence . This is also the first case of the master theorem, since and the additive work is constant.
For the decrementing recurrence, summing from the supplied base at three givesso here as well. Values at the smaller base indices remain one as specified.
For the recurrence that squares its recursive result, set . Then above the base range. LetAfter expansions, , giving the exact answerFor powers of two this is . For arbitrary positive integer , the exact values form plateaux: , while . In general . It is not uniformly over integer : near the top of a plateau the exponent is closer to . Keeping the integer halving is essential; the ordinary linear master theorem does not apply to squaring .
Sequential accumulation writes merged outputs of lengths . Its total work isThe growing list prefix is repeatedly copied, even though its internal order is already known.
Instead, divide the family of arrays into two nearly equal halves, recursively merge each half, and merge the two resulting sorted arrays. A balanced merge tree has levels; at each level at most entries are read or written in merges. Thus the bound is for , including the output work. Equivalently the recurrence in the number of arrays is . The one-array case simply returns it, or costs if a fresh output array is required.
A strict majority element in the whole array must be a strict majority element in at least one half: otherwise summing the two non-majority element frequency bounds would give at most half of all entries. This observation supplies at most two candidates, but they must still be verified in the whole subarray.
majority(A, left, right):
if left == right: return NoMajority
if right - left == 1: return Candidate(A[left])
middle = floor((left + right)/2)
first = majority(A, left, middle)
second = majority(A, middle, right)
for candidate in the two returned tagged results:
if candidate is Candidate(x):
count = 0
for i from left to right-1:
if A[i] == x: count = count + 1
if 2*count > right-left: return Candidate(x)
return NoMajorityNoMajority is a separate result tag, not a possible input element. The two-candidate loop does not require ordering, hashing or conversion of arbitrary elements to a set. It may count the same candidate twice without changing correctness or the bound.Induction proves the recursive candidates correct. If the whole subarray has a majority element, the observation ensures it reaches the verification step; if a candidate passes the strict frequency test, it really is a majority element. The worst-case recurrence has two balanced recursive calls and linear combination work, so the running time is , with auxiliary recursion depth when the array is passed by index ranges. A different cancellation-based method can achieve linear time, but is not needed for this divide-and-conquer construction.
Articles by others on the same topic
There are currently no matching articles.