How to do asymptotic analysis on this weird recurrence?

Question

I came across this weird recurrence equation:

T(n,h) = T(n/2, h1) + T(n/2, h-h1) + nh

and:

T(1,h) = O(h)

I need to find the asymptotic upper bound. I have never come across a recurrence relation with two arguments.

After much searching I found this set of slides which indicates to me that it is related to computational geometry.

It would be nice if someone could point me in the right direction.

Answer 1

Assuming that n is a power of 2, 0 <= h1 <= h, T(0, h) = 0, and T(1, h) = h, an upper bound is 2nh by the following inductive proof.

Basis: T(0, h) <= 0 <= 2(0)h, and T(1, h) <= h <= 2(1)h.

Inductive step: T(n, h) = T(n/2, h1) + T(n/2, h - h1) + nh <= 2(n/2)h1 + 2(n/2)(h - h1) + nh <= 2nh, regardless of h1.

Answer 2

Assuming the first recursive call includes h instead of h1, and replacing h1 by c (for the sake of readability), I decided to proceed like the following: