0
$\begingroup$

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as:

$function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ if \ n = 1\ then\ return (2);\\ else \ return(2*XYZ(\lfloor(XYZ(\lfloor n/2\rfloor)/2\rfloor) - XYZ(\lfloor n/2\rfloor) + XYZ(\lfloor n/2) \rfloor)); $

From that since we have five recursive calls: $$T(n) = 5*T(n/2) + 2n^2$$

Since:$$a = 5 \ b=2 \ d(n) = 2*n^2$$ $$a < d(b) => n^{log_2 d(2))} => \theta(n^3) $$ Time Complexity is then $\theta(8^r) $ which is derived from $n = 2^N$ where $n$ is the number of bits of its binary code.

Am I correct in assuming five recursive calls for the time complexity algorithm? Is the final time complexity correct with respect to bits? Is bounding by five function calls enough or will the upper bound be greater than the tight bound that I calculated?

$\endgroup$
16
  • $\begingroup$ Hem, I count $4$ recursive calls, and they are not all with argument $n/2$... $\endgroup$
    – user65203
    Dec 4 '15 at 10:57
  • $\begingroup$ Is the empty loop intended ? Are the self-canceling calls intended ? $\endgroup$
    – user65203
    Dec 4 '15 at 10:59
  • $\begingroup$ Yes the empty loop is the "driving function". I counted the 5 recursive calls from the fact that we're multiplying the recursive call by 2 plus the inner recursive call and the other two recursive calls. The self cancelling calls are intended, but don't they still factor into the time complexity? $\endgroup$ Dec 4 '15 at 11:08
  • $\begingroup$ The multiplication does not influence the number of calls, hence $4$. And what is $XYZ(n)$ returning ? $\endgroup$
    – user65203
    Dec 4 '15 at 13:27
  • $\begingroup$ $XYZ(1) = 2$ is the base case for the function. If I am considering the nested function call as 1 recursion, is there a reason for changing the argument of the outer function to something other than $n/2$? $\endgroup$ Dec 4 '15 at 13:35
2
$\begingroup$

Hint:

Let us assume $n=2^k$ for convenience.

We first establish the value of $\text{XYZ}(n)$.

By the recursive definition,

XYZ(2) = 2XYZ(XYZ(1)/2)-XYZ(1)+XYZ(1) = 2XYZ(1) = 4,
XYZ(4) = 2XYZ(XYZ(2)/2)-XYZ(2)+XYZ(2) = 2XYZ(2) = 8,
XYZ(8) = 2XYZ(XYZ(4)/2)-XYZ(4)+XYZ(4) = 2XYZ(4) = 16,
...

and obviously $\text{XYZ}(n)=2n$.

Then for $n>1$, a call of $\text{XYZ}$ involves $3$ recursive calls with the argument $\frac n2$, and another with the argument $\frac{\text{XYZ}(\frac n2)}2$, which happens to also be $\frac n2$.

If we count the number of iterations of the empty loop,

$$T(n)=4T\left(\frac n2\right)+2n^2.$$

Try a solution of the form $n^2(a+b\log_2(n))$.

$\endgroup$
5
  • 1
    $\begingroup$ I see where you derived it from now, many thanks for taking the time to write it out. Recursion is not my strongest subject, but you've definitely helped me understand where the T(n) formula is derived from than most of my professors here do. $\endgroup$ Dec 4 '15 at 14:37
  • 1
    $\begingroup$ I must admit that this isn't the simplest of the exercises. $\endgroup$
    – user65203
    Dec 4 '15 at 14:38
  • $\begingroup$ Sorry to bug you Yves, but I'm trying to figure our the complexity class of the basic, non-trivial [M] game and am not sure how to formulate a question that won't be ignored. "Basic non-trivial" means a 9x9 Sudoku. Here are the rules: fundamentalcombinatronics.com/rules-of-m . There is also a mobile app mbrane, which most find more useful than reading the rules. Any guidance would be greatly apprciated. $\endgroup$
    – DukeZhou
    Dec 14 '17 at 17:25
  • 1
    $\begingroup$ @DukeZhou: problems with a fixed size have no asymptotic complexity. They are all $O(1)$. $\endgroup$
    – user65203
    Dec 14 '17 at 23:50
  • $\begingroup$ @YvesDaoust thanks for that! What about problems without fixed size, for instance the same Sudoku boards structure only m^n(m^n)? $\endgroup$
    – DukeZhou
    Dec 15 '17 at 16:20

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.