4
$\begingroup$

If the time complexity $T(n)$ of two functions $x(n)$ and $y(n)$ are mutually recursive, as in Time complexity of mutually recursive functions, this gives $T(n)=O(2^n)$. But how do you measure an algorithm with two or more (4 in the example below) recursive functions that are not necessarily mutually recursive?

Example: Recursive Step Function

$$ \begin{align*} w(n)&= \begin{cases} w(n-1)+1 & \text{if } x(n-1)=y(n-1), \\ w(n-1) & \text{otherwise.} \end{cases} \\ x(n)&=8w(n). \\ y(n)&= \begin{cases} 1 & \text{if } w(n) > w(n-1), \\ y(n-1)+1 & \text{otherwise.} \end{cases} \\ z(n) &= \begin{cases} z(n-1)+1 & \text{if } z(n-1) < y(n-1) \text{ and } z(n-1)=1, \\ z(n-1)-1 & \text{if } z(n-1) < y(n-1) \text{ and } z(n-1)\neq 1, \\ z(n-1) & \text{otherwise.} \end{cases} \end{align*} $$

These functions loop until $w(n)=I$ and then output the value of $z(n)$, where $I$ is the user input value. This input value could be rather large. I get the worse case scenario is dependent on $w(n)$, as it increases slowly.

I have calculated that the function specifically $$w(n)=O\left(\frac{\sqrt{16n+16}}{8}+\frac12\right),$$ but I am new to time complexity. Could anyone help me to understand?

Here is the example in pseudocode:

SET w to 0
SET x to 1
SET y to 1
SET z to 0
GET i
REPEAT 
    IF z<y and z=1 THEN
        z=z+1 
    ELSEIF z<y and z != 1 THEN
        z=z-1
    ELSE do nothing
    IF x=y THEN
        w=w+1 and x=8*w and y=1
    ELSE 
        x=8*w and y=y+1
UNTIL w=i
PRINT z
$\endgroup$
  • $\begingroup$ Are w, x, y, z programs or running-time functions? $\endgroup$ – Raphael Jul 15 '17 at 7:32
  • $\begingroup$ So you're trying to solve recurrences. That's a very different thing from what your title and tags suggest! Do not confuse algorithms and their running-time functions! Writing an algorithm that computes the running-time function is usually meaningless. $\endgroup$ – Raphael Jul 16 '17 at 10:19
  • $\begingroup$ Jeff, @YuvalFilmus, please remove or flag the comments that can go! $\endgroup$ – Raphael Jul 16 '17 at 10:28
  • $\begingroup$ @Jeff Then you've given me contradictory information. Maybe Yuval can edit the question to make sense, since he's apparently understood it. $\endgroup$ – Raphael Jul 16 '17 at 13:41
2
$\begingroup$

You can prove by induction that it always holds that $z \leq 0$, and so $z \neq 1$ and $z < y$. This allows the following simplification:

  • Input: $i$
  • $x,y,z,w \gets 1,1,0,0$
  • Repeat:
    • $z \gets z-1$
    • If $x = y$ then $w \gets w+1$ and $y \gets 1$; Else $y \gets y+1$
    • $x \gets 8w$
  • Until $w = i$
  • Return $z$

The running time is proportional to the number of iterations of the loop (which also happens to be the negation of the output).

In the first iteration we have $x=y$ and so set $w\gets 1$, $x\gets 8$, $y\gets 1$. Eight iterations later, we have $x=y=8$ (at the beginning of the iteration), and so we set $w\gets 2$, $x\gets 16$, $y\gets 1$. Sixteen iterations later, we have $x=y=16$, and so we set $w\gets 3$, $x\gets 24$, $y\gets 1$.

In total, we see that the number of iterations is $$ 1 + 8(1 + \cdots + (i-1)) = 1 + 8\frac{i(i-1)}{2} = 4i(i-1)+1 = (2i-1)^2. $$ This shows that the output is $-(2i-1)^2$, and that the running time is $\Theta(i^2)$.

$\endgroup$

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.