What's the (asymptotic) solution of the recurrence $T(n,m,k,t)\leq T(n^\frac 1 m, 1, km, kt) + \Theta(n)$?

I know how to solve univariate recurrences, but this recurrence is much more difficult, so I am stuck here.

The solution of this inequality should be something that does not imply any "dependency" between $n,m,k,t$. For example, subtituting the solution $T(n,m,k,t)=n^\frac k m$ yields $n^\frac m k\leq n^k$ which is true for every $n,m,k,t\geq 1$, while $T(n,m,k,t)=nk$ implies $nk\leq n^\frac 1 m km$ which is equaivalent to $n\leq n^\frac 1 m m$ which is not always true, and thus implies some dependency between $n,m$. Therefore, this solution holds only in special cases that satisfy this dependency.

I believe that the set of solutions of this inequality is a subset of the set of solutions that @D.W. has shown (as some of which are true only assuming some dependency between $m,n,k,t$).

  • 2
    $\begingroup$ What is/are the base case(s)? What have you tried so far? $\endgroup$ – ryan May 9 '17 at 21:15
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael May 9 '17 at 22:58
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael May 9 '17 at 22:58
  • $\begingroup$ 1) Calling this thing a recurrence is stretching terminology. 2) What do you know about how the parameters relate to each other? Why is $T$ well-defined? $\endgroup$ – Raphael May 9 '17 at 22:59

There isn't enough information to provide a solution. See explanation below.

Let $c>0$ be a constant so that $T(n,m,k,t) \le T(n^{1/m},1,km,kt) + cn$. When we unroll your recurrence twice, we find that

$$T(n,m,k,t) \le T(n^{1/m},1,km,kt) + cn \le T(n^{1/m},1,km,k^2mt) + 2cn.$$

Unroll $r$ times, and we find that

$$T(n,m,k,t) \le T(n^{1/m},1,km,k^r m^{r-1} t) + rcn.$$

This terminates at a base case when $k^r m^{r-1} t = 1$, which is equivalent to $(km)^r = m/t$. Taking logs, we find that this happens when

$$r = {\log(m/t) \over \log(km)}.$$

Thus we find

$$T(n,m,k,t) \le T(n^{1/m},1,km,1) + {\log(m/t) \over \log(km)}cn.$$

Let $f(x,y)$ be a function of $x,y$. Then

$$T(n,m,k,t) = \Theta(f(n^{1/m},km) + {\log(m/t) \over \log(km)}n)$$

is a possible solution of this recurrence (simply take $T(x,1,y,1) = f(x,y)$), as is any asymptotically smaller function. To determine whether this is actually a feasible solution, plug into the definition above and check whether it satisfies your inequality for all $n,m,k,t$.

Is there a solution that is polynomial in $n$? Yes, for instance $T(n,m,k,t) = n$ is easily verified to satisfy your inequality for all $n,m,k,t$ and to be polynomial in $n$. Also $T(n,m,k,t)=n^2$ or indeed $T(n,m,k,t)=n^d$ for any constant $d$ is a solution.

| cite | improve this answer | |
  • $\begingroup$ Do you have any assumptions on $f$? (because taking $f(x,y)=\Theta(1)$, for example, gives a wrong solution to my understanding) $\endgroup$ – Dudi Frid May 10 '17 at 6:50
  • $\begingroup$ @DudiFrid, why do you think that gives a wrong solution? It looks to me like the resulting solution is consistent with all of the information in the question. $\endgroup$ – D.W. May 10 '17 at 19:21
  • $\begingroup$ Taking $f(x,y)=c$ for some constant $c$, gives $c+\frac {\log(m/t)}{\log (km)}n\leq d+\frac {\log(1/kt)}{\log (km)}n^\frac 1 m$ for some constant $d$. Thus, $\log(m/t)n\leq d+n^\frac 1 m$, but assuming that the inputs of $T$ (i.e, $n,m,k,t$) are "independent", we get inequality that is not true, because it shows a dependency between them. Thus, I think that the inequality in my post that shows no dependency between these inputs, is not equivalent to what you've written. $\endgroup$ – Dudi Frid May 11 '17 at 20:38
  • $\begingroup$ @DudiFrid, if you forgot to include something in the question, please edit the question to clarify. $\endgroup$ – D.W. May 11 '17 at 21:21
  • $\begingroup$ OK, I edited my question $\endgroup$ – Dudi Frid May 12 '17 at 10:03

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.