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, 2015 at 10:57
  • $\begingroup$ Is the empty loop intended ? Are the self-canceling calls intended ? $\endgroup$
    – user65203
    Dec 4, 2015 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, 2015 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, 2015 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, 2015 at 13:35

1 Answer 1

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, 2015 at 14:37
  • 1
    $\begingroup$ I must admit that this isn't the simplest of the exercises. $\endgroup$
    – user65203
    Dec 4, 2015 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, 2017 at 17:25
  • 1
    $\begingroup$ @DukeZhou: problems with a fixed size have no asymptotic complexity. They are all $O(1)$. $\endgroup$
    – user65203
    Dec 14, 2017 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, 2017 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.