An integer-valued problem size requires integer subproblem sizes and a base case. For the displayed unequal split with , both children have positive size less than , and . The entropy potential for a divide-and-conquer recurrence therefore supplies a uniform positive potential decrease. The squared sizes satisfy , which similarly closes a quadratic inductive hypothesis when the work at the root is .
Articles by others on the same topic
There are currently no matching articles.