2
$\begingroup$
def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc( RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2) )

How should I start if it is nested inside? I know how to solve it without the outer RecFunc (with a recursive tree I assume) - But here there is an outer RecFunc and I don't know what to do!


Thanks to Steven for noticing a mistake I made (Misread the question and made it so RecFunc(4) will not halt)

$\endgroup$
2
  • $\begingroup$ RecFunc(3) calls RecFunc(3), so this code still doesn't halt. $\endgroup$
    – Steven
    Commented Feb 13, 2021 at 18:08
  • $\begingroup$ @Steven Forgot to edit the base case again.. so sorry.. a dumb mistake by me, is it ok now? if it still doesnot halt for some value of $n$ I need to ignore them and calculate a strict $\Theta$ value of the running time complexity and space $\endgroup$
    – CSch of x
    Commented Feb 13, 2021 at 18:16

2 Answers 2

2
$\begingroup$

Notice that the outer RecFunc call is just a "decoy" thrown in there to make the exercise seem more complicate than it is. Indeed, it is irrelevant as far as the asymptotic time complexity is concerned. This is because every call to RecFunc eventually returns $1$ (that's the only possible returned value, you can prove by induction that RecFunc eventually returns), and therefore the last (outer) call to RecFunc will just be RecFun(3), which terminates in constant time. We can charge this constant time to the caller function. Since the caller is going to spend $\Theta(1)$ time anyway, this doesn't change anything.

Then you want to analyze:

def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2)

Whose running time is described by the recurrence equation: $$ T(n)=2T(n/2) + T(n/3) + \Theta(1), $$

which can be solved using the Akra–Bazzi method. Let $p$ such that: $ 2 \cdot \frac{1}{2^p} + \frac{1}{3^p} = 1. $ Clearly $p>0$. Then: $$ \int_{u=1}^n \frac{1}{u^{p+1}} \mathrm{d}u = \int_{u=1}^n {u^{-p-1}} \mathrm{d}u = -\frac{1}{p} \cdot \left| u^{-p} \right|_{u=1}^n = \frac{1}{p} \cdot \left( 1 - \frac{1}{n^p} \right) = \Theta(1), $$ and you have: $T(n) = \Theta(n^p)$. An approximation of $p$ is $1.3646$.

The space complexity is clearly $\Theta(\log n)$ since this is the maximum recursion depth.

$\endgroup$
3
  • $\begingroup$ Sorry, I misread the question, I will edit it. I am so sorry! (You can keep this answer because it is a good point) Thank you sir! $\endgroup$
    – CSch of x
    Commented Feb 13, 2021 at 17:36
  • $\begingroup$ Isn't it $ 2 \cdot \frac{1}{2^p} + \frac{1}{3^p} = 1 $ ? $\endgroup$
    – CSch of x
    Commented Feb 13, 2021 at 21:58
  • 1
    $\begingroup$ Yes, sorry. I'll edit the answer. $\endgroup$
    – Steven
    Commented Feb 13, 2021 at 22:03
0
$\begingroup$

It’s obvious that recfunc(n) + 1 if n <= 3, then if n <= 6, n <= 12 etc. So recfunc(n) = 1 for all b, so we can calculate it in O(1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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