0
$\begingroup$

I am trying to do the recurrence relation for my algorithm, but it has two variables $T(n,m)$. For sufficiently small $n$, $m$ is practically the same as $n$, but $m$ cannot grow beyond some constant $k$. So once $n$ grows beyond $k$, $m$ turns to constant $k$. So it has two different stages.

I have done the relation in both cases: when $m$ is another variable, and when $m$ is a constant, but how do I put them together?

Using $a=2, b=2$ as an example: this recurrence relation with $m$ as a variable like $n$: $$T(1)=1$$ $$\begin{equation*} \begin{split} T(n) & = 2T(\frac{n}{2})+m \\ & = 2T(\frac{n}{2})+n\\ & = n+nlog_2n \end{split} \end{equation*}$$

Treating $m$ as a constant: $$\begin{equation*} \begin{split} T(n) &= 2T(\frac{n}{2})+m \\ &= n+mn-m \end{split}\end{equation*}$$

Please feel free to check my math. Now how do I represent this as one recurrence relation? $m$ cannot grow beyond constant $k$.

$\endgroup$
1
$\begingroup$

Just solve both cases separately. I.e., consider cases for $m < k$ and $m = k$ separately. The solution for the first one (i.e., $T(n, k - 1)$) gives the starting point for the second recurrence (i.e., $T'(n) = T(n, k)$, presumably for $n \ge k$).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.