Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$

Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have been written above as $n_{i,n,m}$ and $m_{i,n,m}$, but they are written above as $n_i$ and $m_i$ in a way of abbreviation for more readablity.

Let us assume that $T$ is non-decreasing w.r.t $n$, and non-increasing w.r.t $m$.

I am looking for a useful, necessary and sufficient condition so that $\exists k. T(n,m)=O\bigg(\Big(\log(m)+n\Big)^k\bigg)$

The importance of such conditions stems from their applicabilty in concluding super-polynomial lower bounds on complex recurrences of the above-mentioned form.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.