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)&amp;=
\begin{cases}
w(n-1)+1 &amp; \text{if } x(n-1)=y(n-1), \\
w(n-1) &amp; \text{otherwise.}
\end{cases} \\
x(n)&amp;=8w(n). \\
y(n)&amp;=
\begin{cases}
1 &amp; \text{if } w(n) &gt; w(n-1), \\
y(n-1)+1 &amp; \text{otherwise.}
\end{cases} \\
z(n) &amp;=
\begin{cases}
z(n-1)+1 &amp; \text{if } z(n-1) &lt; y(n-1) \text{ and } z(n-1)=1, \\
z(n-1)-1 &amp; \text{if } z(n-1) &lt; y(n-1) \text{ and } z(n-1)\neq 1, \\
z(n-1) &amp; \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&lt;y and z=1 THEN
        z=z+1 
    ELSEIF z&lt;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
You can prove by induction that it always holds that $z \leq 0$, and so $z \neq 1$ and $z &lt; 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)$.