2
$\begingroup$

I'm trying to solve the following recurrence relation (Strassen's):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} $$ So I multiplied the $7$ by $2$ several times and the 18n^2^2 several times and ended up with this general equation:- $$ 7k T(n/2^k) + 18n^2k $$ but, well, firstly, is this correct? and also, how do I find the value of k from that beast?!

Many thanks in advance everyone, I really appreciate all your help.

$\endgroup$
  • 1
    $\begingroup$ I reformatted your question. Please check and make sure that I didn't change what your are asking. $\endgroup$ – Thomas May 2 '13 at 19:22
  • $\begingroup$ This relation doesn't appear to be well-defined. How can we calculate $T(3)$, for instance? $\endgroup$ – vadim123 May 2 '13 at 19:28
  • $\begingroup$ thank you thomas, it reads much better now! $\endgroup$ – SexySarah May 2 '13 at 19:38
  • $\begingroup$ Can't you use the Master Theorem for that? $\endgroup$ – skrtbhtngr Sep 15 '16 at 19:30
4
$\begingroup$

Write $n = 2^k$ and define $U_k = T(2^k)$. The relation beocmes

$$U_k - 7\, U_{k-1} = 18 \cdot 2^{2 k}$$

with the initial condition being

$$U_1 = 1$$

I broke the equation up into a homogeneous solution and an particular solution, then applied the initial condition, as follows:

$$U_k = H_k + P_k$$

$$H_k - 7 H_{k-1} = 0 \implies H_k = A \cdot 7^k$$

Choose $P_k = B \cdot 4^k$; then

$$B \cdot 4^k - \frac{7}{4} B \cdot 4^k = 18 \cdot 4^k \implies B = -24$$

Then $U_k = A \cdot 7^k - 24 \cdot 4^k$. Use $U_1=1$ to get that

$$7 A - 96 = 1 \implies A = \frac{97}{7}$$

The result is

$$U_k =97 \cdot 7^{k-1} -96 \cdot 4^{k-1}$$

To recover $T(n)$, substitute $k=\log_2{n}$ into $U_k$. The result is

$$T(n) = \frac{97}{7} n^{\log_2{7}} - 24 n^2$$

$\endgroup$
  • $\begingroup$ Please could you go into more detail with the steps you took to get there? I just don't understand now $\endgroup$ – SexySarah May 2 '13 at 19:51
  • $\begingroup$ @SexySarah: steps added $\endgroup$ – Ron Gordon May 2 '13 at 20:06
  • $\begingroup$ @SexySarah: no problem. As you are new to M.SE, just remember that, if you find a solution useful, please accept it by clicking the checkmark underneath the number to the left of the solution. $\endgroup$ – Ron Gordon May 2 '13 at 20:42
  • $\begingroup$ all done, hope that helps $\endgroup$ – SexySarah May 2 '13 at 21:48
0
$\begingroup$

We can actually obtain exact values for $T(n)$ for all values of $n$ and not just powers of two.

Start by working with the alternate recurrence relation $$S(n) = 7 S(\lfloor n/2 \rfloor) + 18n^2$$ where $S(0) = 0.$

Let the binary representation of $n$ be given by $$ n = \sum_{k=0}^{\lfloor \log_2 n\rfloor} d_k 2^k.$$

Then it is not difficult to see that the exact value of $S(n)$ is given by $$ S(n) = 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j \left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^{k-j}\right)^2.$$

Now to get an upper bound on $S(n)$ consider the case where $n$ consists of all one digits, giving $$ S(n) \le 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j \left( \sum_{k=j}^{\lfloor \log_2 n\rfloor} 2^{k-j} \right)^2 = \frac{441}{5} 7^{\lfloor \log_2 n\rfloor}-96 \times 4^{\lfloor \log_2 n\rfloor} + \frac{144}{5} 2^{\lfloor \log_2 n\rfloor} -3.$$ For a lower bound, take $n$ to be a one digit followed by zeros, giving $$ S(n) \ge 18 \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j (2^{\lfloor \log_2 n\rfloor-j})^2 = 42 \times 7^{\lfloor \log_2 n\rfloor} - 24 \times 4^{\lfloor \log_2 n\rfloor}.$$

We still need to account for the fact that $T(0)=1, T(1)=1$ and $T(2)=1.$ A simple calculation shows that $$ T(n) = S(n) - \frac{197}{7} 7^{\lfloor \log_2 n\rfloor} d_{\lfloor \log_2 n\rfloor} + 78 \times 7^{\lfloor \log_2 n\rfloor-1} d_{\lfloor \log_2 n\rfloor-1}.$$ This formula is exact and holds for all $n\ge 3$.

Finally to get the asymptotics look at the two leading terms from the lower and upper bounds. The first is $$\Theta\left(7^{\lfloor \log_2 n\rfloor}\right) = \Theta(2^{\log_2 7 \log_2 n}) = \Theta(n^{\log_2 7}).$$

$T(n)$ fluctuates around this value with the coefficient at most for strings of ones $$\frac{1}{7} \left(\frac{441}{5} - \frac{197}{7} + \frac{78}{7} \right)= \frac{356}{35}$$ and at least $$ 42 - \frac{197}{7} = \frac{97}{7}.$$ The next term in the asymptotic expansion is $$\Theta\left(4^{\lfloor \log_2 n\rfloor}\right) = \Theta(n^2),$$ with the coefficient between $24$ and $96.$

$\endgroup$
  • $\begingroup$ There is more on this method here. $\endgroup$ – Marko Riedel May 2 '13 at 23:45
  • $\begingroup$ Marko: I have no idea whether your analysis is correct or not; it seems a bit above my pay grade. But I do have a bit of unsolicited advice. I have gone through all of your posts, and you consistently state your exact result in terms of a deux ex machina: "Then it is not difficult to see that the exact value of $S(n)$ is given by..." For whom are you presenting your results? Certainly not @SexySarah, who requested details of how I solved a simple, first-order linear recurrence. I get the impression that you need another audience. If not, then fill in details for us Neanderthals. $\endgroup$ – Ron Gordon May 3 '13 at 15:18
  • $\begingroup$ @RonGordon. The part about it being easy to see above refers to the fact that the proof of the equation does not involve any theorems or require additional manipulation, it simply encapsulates and represents the facts. $\endgroup$ – Marko Riedel May 3 '13 at 19:12
  • $\begingroup$ @RonGordon. Thanks very much for alerting me to this problem. The trouble with the tone is something that ocurrs frequently when translating from the German and I try to avoid this effect whenever possible. As for deus ex machina, that should refer to Maple, which I use to verify all my calculations. The availability of various CAS makes it possible to omit the more tedious part from a calculation, while giving the reader powerful tools to recapitulate them if needed. And finally, can you suggest alternate places? For first/second year comp. sci. level stackexchange is a good match. $\endgroup$ – Marko Riedel May 3 '13 at 19:17

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.