Where Divide and Conquer Spends Its Time

A divide-and-conquer algorithm splits a problem of size n into a subproblems of size n / b and spends n^{k} work combining their answers:

Summing the recursion tree, one of three things happens. Return which, as a string:

• "leaves" — the bottom level dominates, so T(n) = \Theta(n^{\log_b a});
• "balanced" — every level costs the same, so T(n) = \Theta(n^{k}\log n);
• "top" — the first combine dominates, so T(n) = \Theta(n^{k}).

Examples

Input:  a = 2, b = 2, k = 1
Output: "balanced"
Explanation: merge sort, Theta(n log n).

Input:  a = 3, b = 2, k = 1
Output: "leaves"
Explanation: Karatsuba multiplication; three halves beat one linear merge.

Constraints

• 1 <= a <= 10**6, 2 <= b <= 10**6, 0 <= k <= 20
• Compare a with b ** k exactly; log(a) / log(b) is not reliable here.

Goals

• Compare the work at the leaves of a recursion tree with the work at its root
• Decide the three cases by integer arithmetic instead of floating-point logarithms
• Recognise familiar algorithms in their recurrences