# Solving a system of recurrences

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

• Are w, x, y, z programs or running-time functions? – Raphael Jul 15 '17 at 7:32
• 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. – Raphael Jul 16 '17 at 10:19
• Jeff, @YuvalFilmus, please remove or flag the comments that can go! – Raphael Jul 16 '17 at 10:28
• @Jeff Then you've given me contradictory information. Maybe Yuval can edit the question to make sense, since he's apparently understood it. – Raphael Jul 16 '17 at 13:41

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