Solving a recurrence relation using Z transform

2,326

The calculation of the $Z$ transform above is not correct. For example, the equation $$ Z[T(n)-n]=\frac{Z[T(n)]}{z^{n}} $$ is not correct. Instead, you have $$ Z[T(n)-n] = Z[T(n)] - Z[n] = Z[T(n)] - \frac{z}{(1-z)^2} $$ which, when substituted into $$Z[T(n)]=Z[T(n)-n]+\frac{z}{(z-1)^{2}}$$ results in the trivial $$ Z[T(n)]=Z[T(n)]. $$ To obtain a nontrivial equation for $Z[T(n)]$, you have to first express the $Z$ transforms of $T(\lfloor n/4 \rfloor)$ and $T(\lfloor 3n/4 \rfloor)$ in terms of the $Z$ transform of $T(n)$ (taking $T(n)$ here to be an arbitrary sequence), and then use the recurrence to express $Z[T(n)]$ in terms of the $Z$ transforms of $T(\lfloor n/4 \rfloor)$ and $T(\lfloor 3n/4 \rfloor)$, also taking into account the initial values $T(1)=T(2)=T(3)=1$. Although it is possible to do this, the expressions that result are rather complex, so it would be difficult to solve this problem directly using the $Z$ transform.

Using a result of S. Roura ("An improved master theorem for divide-and-conquer recurrences", S. Roura, 1997) it is possible to show that $$ T(n)\sim C_0 n \ln n, \qquad \text{where } C_0=-(\frac 14 \ln \frac 14+\frac 34 \ln \frac 34)^{-1} \approx 1.77829895. $$ Also, a generalized form of the recurrence for $T(n)$ is analyzed by Drmota and Szpankowski in "A master theorem for discrete divide and conquer recurrences", 2011. Their Theorem 2.1 also shows in this case that $T(n)\sim Cn\ln n$ for some constant $C$.

For $C_0$ as above, it is straightforward to show by induction that $T(n)\le C_0 n\ln n$ for all $n\ge 2$. This can be checked directly for $2\le n\le 7$. Then, if $n\ge8$, \begin{eqnarray*} T(n)&=&T(\lfloor \frac n4 \rfloor)+T(\lfloor \frac{3n}4\rfloor)+n\\ &\le& C_0 (\lfloor \frac n4 \rfloor \ln \lfloor \frac {n}4 \rfloor)+ C_0 (\lfloor \frac{3n}4 \rfloor \ln \lfloor \frac {3n}4 \rfloor)+ n,\\ &\ & \qquad \qquad \text{by the induction hypothesis}\\ &\le& C_0 (\frac n4 \ln \frac {n}4 )+C_0(\frac {3n}4 \ln \frac{3n}4) + n\\ &=& C_0 (\frac n4 \ln n + \frac {3n}4 \ln n + \frac n4 \ln \frac 14 + \frac {3n}4 \ln \frac 34) + n\\ &=& C_0 n \ln n + C_0 ( \frac 14 \ln \frac 14 + \frac {3}4 \ln \frac 34)n + n\\ &=& C_0 n \ln n, \end{eqnarray*} completing the induction.

Share:
2,326

Related videos on Youtube

user1489886
Author by

user1489886

Updated on August 01, 2022

Comments

  • user1489886
    user1489886 over 1 year

    I'm trying to solve the following recurrence using Z transforms:

    For $n\in \mathbb{N}^{*}$

    $T(n)=1\ for\ n< 4$

    $T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n\ for\ n\geq 4$

    I should find an expression for T(n).

    Using $Z[T(n)](z)$ as the Z transform for T(n) (or more simply, just $Z[T(n)]$), I have arrived to the following solution attempt:

    $Z[T(n)]=Z[T(\lfloor \frac{n}{4} \rfloor)]+Z[T(\lfloor \frac{3n}{4} \rfloor)]+\frac{z}{(z-1)^{2}}$

    Using the property of linearity of any Z transformation we can add the arguments of the first two terms of the right side and get the following:

    $Z[T(n)]=Z[T(\frac{n}{4})+T(\frac{3n}{4})]+\frac{z}{(z-1)^{2}}$

    or

    $Z[T(n)]=Z[T(n)-n]+\frac{z}{(z-1)^{2}}$

    I guess that the first term of the right side of the equation is just $Z[T(n)]$ shifted to the right with n units, and so it can be written as follows:

    $Z[T(n)-n]=\frac{Z[T(n)]}{z^{n}}$

    Therefore, the equation becomes

    $Z[T(n)]=\frac{Z[T(n)]}{z^{n}}+\frac{z}{(z-1)^{2}}$

    By subtracting from both sides of the equation the first term of the right side we get:

    $Z[T(n)]\cdot \frac{z^{n}-1}{z^{n}}=\frac{z}{(z-1)^{2}}$

    and therefore

    $Z[T(n)]=\frac{z^{n+1}}{(z-1)^{2}\cdot (z^{n}-1)}$

    Now the problem is that it is very difficult for me to reverse transform this (I don't even know how to find a value for the convergence radius). I have a strong feeling that I was wrong somewhere along the way, so I would like to know if there is a better way to do this using Z transforms.

    And if there is not the case, can anybody please explain to me if Z transforms can be used at all to solve this equation?

    And if not, can anybody please tell me if there is a way to calculate an upper bound for T(n) (which is reasonably low)?

  • user1489886
    user1489886 over 10 years
    When I was thought the Z transform they told me I could use it to solve any constant coefficient recurrence and I wanted to get its money's worth. Thanks for the useful answer. That induction provided a nice approach.