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$
4
  • $\begingroup$ Are w, x, y, z programs or running-time functions? $\endgroup$
    – Raphael
    Jul 15, 2017 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, 2017 at 10:19
  • $\begingroup$ Jeff, @YuvalFilmus, please remove or flag the comments that can go! $\endgroup$
    – Raphael
    Jul 16, 2017 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, 2017 at 13:41

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.