Time Complexity

Question

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?

Answer 1

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))$.