I am analyzing some kind of construction for which size satisfies the following recursion:
$P(n,k)=\frac{k}{2}\log \frac{k}{2} + 1 + \frac{n}{2} + P(\frac{n}{2},k) + P(\frac{n}{2},\frac{k}{2})$
$P(k,k)=\frac{1}{4}k\log^2k - \frac{1}{4}k\log k + k - 1$
$P(n,1)=n-1$
We assume that $k\leq \frac{n}{2}$. We also assume for simplicity that $n$ and $k$ are powers of 2. Also $\log = \log_2$
I tried using generating functions but all I got was some gibberish. It is possible that I made some mistake.
Can someone point me to the techniques I could use to attack this recursion? Note that it does not need to be an exact solution. It can be some approximation, but not with big-O notation. That I already know it is going to be $O(n\log^2 k)$. But this is not enough for my purposes.