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$
  • $\begingroup$ Hem, I count $4$ recursive calls, and they are not all with argument $n/2$... $\endgroup$ – Yves Daoust Dec 4 '15 at 10:57
  • $\begingroup$ Is the empty loop intended ? Are the self-canceling calls intended ? $\endgroup$ – Yves Daoust 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$ – Jakub Kawalec 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$ – Yves Daoust 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$ – Jakub Kawalec 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$
  • 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$ – Jakub Kawalec Dec 4 '15 at 14:37
  • 1
    $\begingroup$ I must admit that this isn't the simplest of the exercises. $\endgroup$ – Yves Daoust 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$ – Yves Daoust 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.