Tightest Bounds for Recurrance

Question

In my Algorithms class we're learning about recurrences, but I'm completely lost and have no idea what to do. I found this pdf from Bowdoin Solving Recurrences with the Iteration/Recursion-tree and it explains it a bit better but the examples provided don't include Big Oh. Two of the problems I have to solve are listed below. I would appreciate it if someone would be able to explain what to do in the case of Big Oh involving recurrences. Thank you

$$T(n) = 8T(n/4) + O(n)$$ $$T(n)=T(n−4)+O(n^2)$$

Answer 1

$T(n) = 8T(n/4) + O(n)$

We can apply the following trick. Put $f(n)=T(n)-T(n/4)$. Then we have $f(n)=O(n)$ and (provided $n/4$ stands for $\lfloor n/4\rfloor$ or $\lceil n/4\rceil$, and $f$ is asymtotically positive) we can apply master method.

We have $a=8$, $b=4$, $\log_b a=3/2$, $f(n)=O(n^{3/2-\varepsilon})$ for $\varepsilon=1/2$. Thus $T\in \Theta(n^{3/2})$.

Slides were taken from a lecture “Solving Recurrences” of block course “Algorithms and Data Structures” (winter term 2014/15) By Prof. Dr. Alexander Wolff.

$T(n)=T(n−4)+O(n^2)$

We have $T(n)-T(n-4)=O(n^2)$, thus there exists $c>0$ such that $T(n)\le cn^2$ for each $n\ge 1$. Pick $d\ge \tfrac 5{12}c$ such that $T(n)\le dn^3$ for all $n\le 4$ and prove by induction that $T(n)\le dn^3$ for all $n\ge 5$. For this it suffices to remark that $dn^3\ge d(n-4)^3+cn^2$.

Answer 2

There are 3 known ways to solve these recurrences:the substitution method, recurrence trees, and the Master Method. Certain conditions must be fulfilled in order to apply this method on a particular recurrence. To use the Master Method, the recurrence must be on the the following form:

$aT(\frac{a}{b}) + f(n)$

Therefore, the first recurrence presented can be solved using the Master Method.

Using the Master Method, three different solutions exist based on the following test computation:

$n^{log_b(a)}$

Based on this computation, three different solutions exist:

1. $T(n) = \Theta(n^{log_b(a)})$, if $f(n) = O(n^{log_b(a)})$
2. $T(n) = \Theta(n^{log_b(a)}log_2(n))$, if $f(n) = \theta(n^{log_b(a)})$
3. $T(n) = \Theta(f(n))$, if $f(n) = \Omega(n^{log_b(a)})$ and there exists a $C$, such that $C < 1$ and $af(\frac{n}{b}) \leq Cf(n)$

Recurrence 1

For the first recurrence present, we can use the test computation to figure out which solution to use.

$n^{log_4(8)} = n^{1.5}$

Since $f(n) = n$, we use solution number 1. Therefore, the solution for the first recurrence is $T(n) = \Theta(n^{1.5})$.

Recurrence 2

For this recurrence, we use the substitution method. This method is more complicated than the Master Method and takes more time. The substitution method works by inserting the function definition inside the recursive call. This is done several times until a pattern is recognizable.

$T(n) = T(n - 4) + n^2$

$T(n) = (T(n - 8) + (n - 4)^2) + n^2 = (T(n - 8) + n^2 - 8n + 16) + n^2 = T(n - 8) + 2n^2 - 8n + 16$

$T(n) = (T(n - 12) + (n - 8)^2) + 2n^2 - 8n + 16 = (T(n - 12) n^2 - 16n + 64) + 2n^2 - 8n + 16 = T(n - 12) + 3n^2 - 24n + 80$

By now, it should be possible to see a pattern. We use the variable $i$ that holds the iteration value. We can now rewrite the recurrence.

$T(n) = T(n - 4i) + in^2 - a + 4^i + b$

As seen above, we have simplified parts of the recurrence using $a$ and $b$, since these values are way smaller than any other part of the recurrence. Now, we use the base value to compute the complexity of the recurrence. This base value is the smallest value. Since we subtract by 4 in the recursive call, the base value must be 4 in order to get 0.

This can be found by the following equation to find $i$.

$n - 4i = 0 \implies n = 4i \implies i = \frac{n}{4}$

This equation describing $i$ can now be inserted into the recurrence.

$T(n) = T(0) + (\frac{n}{4})n^2 + 4^{\frac{n}{4}} = 1 + \frac{n^3}{4} + \sqrt[4]{4^n} \leq \Theta(n^3)$