1
$\begingroup$

How do I go about solving this? When I try to google examples I only see problems with "+1" or "+n" constants and never anything above that.

If possible could anyone also describe the suggest method to solve these as well?

𝑇(𝑛) = 3𝑇(𝑛 − 1) + 3

𝑇(𝑛) = 2𝑇 (𝑛/8) + 4𝑛^2

Update: I couldn't find any examples or helpful resources for solving recurrences with "weird" constants so I figured it would be unique enough to ask here.

$\endgroup$
1
  • $\begingroup$ Guess a solution, prove by induction. You can also "expand" the recursion a few times to get an intuition on what the "guessing" from earlier should be. $\endgroup$ Jul 3, 2016 at 6:05

2 Answers 2

1
$\begingroup$

Take the first example. Start calculating T (100) = T (98) + 4 = T (96) + 4 + 4 = T (94) + 12 = T (92) + 16 ...

Seriously, that's the first thing you do. You have a problem, you try what happens. At this point it should be absolutely obvious to you what happens, right? I hope I don't have to write down the solution?

The next one: T (100) = 3 T (99) + 3 = 9 T (98) + 9 + 3 = 9 * T (98) + 12 = 27 * T (97) + 39 = 81 * T (96) + 120 ... Slightly more complicated, but you see that one of the numbers is a power of 3, and the other one is slightly less obvious $(3^k - 3) / 2$. Figure it out from there.

The next one: Well, I'll start with 512. T (512) = $2 T (64) + 4 * 512^2$ $2 * (2 T (8) + 4 * 64^2) + 1024^2$ = $4 T (8) + 8 * 64^2 + 4 * 512^2$ = $4 * (2 T (1) + 4 * 8^2) + 8 * 64^2 + 4 * 512^2$ = $8 T (1) + 8 * 8^2 + 8 * 64^2 + 4 * 512^2$ - it should be clear what the dominating factor is in this equation.

This is all mathematically trivial. All you had to do to solve these problems is to not look at them and be stunned by the strange formulas but having a go and starting to calculate and see what happens.

PS. The answer was intended to demonstrate that seemingly hard problems can often be attacked quite easily, that overcoming your fear of the unknown and jumping in and seeing what happens is often enough. That is much, much more important than solving one particular problem. You may call this a "waste of time", but I Don't Think So.

The quoted "reference answer" may answer the question, but doesn't inspire anyone to try finding the answer themselves.

$\endgroup$
3
  • $\begingroup$ Note that we have a reference question for such questions. You may want to check our collection before wasting time on answering homework-style questions. $\endgroup$
    – Raphael
    Jul 3, 2016 at 9:46
  • $\begingroup$ Is what you're doing called the iterative method? $\endgroup$
    – Mikael
    Jul 4, 2016 at 0:28
  • $\begingroup$ Not a clue. I call it the "just give it a go" method. Every problem gets solved by giving it a go, and not doing it means you will never learn how to do anything yourself. $\endgroup$
    – gnasher729
    Jul 5, 2016 at 9:16
0
$\begingroup$

Its all about manipulating the equation into a form you understand.

If we say $T(n) = T(n-2) + 4$, all we mean is that $T(n)$ is four larger than it was when n is two less, regardless of n. For a given n, we are therefore just adding on 4s in a linear way for every other n. This is the same as going up by 2 for each term.

$T(n) = 2n + c$ fulfills this. Asymptotically, this is $O(n)$.

The same idea applies to your other equations, that we just need to understand what your recursive function is stating to decide a form that we can use.

For $T(n) = 3T(n-1) + 3$ we separate the two sides and solve for each.

$3T(n-1$) triples every time, so it follows $T^3$, and $+ 3$ adds three every time, so we have $3n$.

Therefore, we decide $T(n) = c(T^3) + 3n + d$. Which asymptotically is just O(n^3)

We can leave the third for practice, but the ideas still apply (note that $2T(n/8)$ doubles every 8 values of n).

$\endgroup$
4
  • $\begingroup$ The truth is somewhat more subtle then you indicate. $\endgroup$ Jul 2, 2016 at 22:39
  • $\begingroup$ @YuvalFilmus, I'm not sure I understand what you mean. Is there a problem with one of my solutions, or my explanation, or both? I haven't taken formal courses in algorithms or discrete math yet, but I have read some textbooks and practice proofs with well known algorithms, and so this is just the approach that seems intuitive to me, is there a better way to solve this? $\endgroup$
    – rp.beltran
    Jul 2, 2016 at 23:50
  • $\begingroup$ For example, in the second case you can't separate the exponential and the linear, though by chance the answers agree. In the third case, if we change the parameters we can foil your intuition completely; see the master theorem. $\endgroup$ Jul 3, 2016 at 6:35
  • $\begingroup$ Note that we have a reference question for such questions. You may want to check our collection before wasting time on answering homework-style questions. $\endgroup$
    – Raphael
    Jul 3, 2016 at 9:46

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