How would I go about calculating the runtime of this algorithm, so I can solve similar questions in the future?
For input size n satisfies the recurrence relation (for n>= 1)
T(n) = (2/n) * (T(0) + T(1) + ... + T(n-1)) + 5n
-
This Tutorial will help you. It explains clearly each and every step.thebignoob– thebignoob2014-04-26 00:36:11 +00:00Commented Apr 26, 2014 at 0:36
-
Thank you, this is perfect! But I am still struggling with the format, How do I start this analysis, the "..." is throwing me off.Ofek– Ofek2014-04-26 00:48:41 +00:00Commented Apr 26, 2014 at 0:48
-
Start considering n=5,6,7.., then you might end up solving what you need :)thebignoob– thebignoob2014-04-26 00:57:39 +00:00Commented Apr 26, 2014 at 0:57
-
Do I just write the first case as (2/n)(T(n-1)+5)?Ofek– Ofek2014-04-26 00:58:12 +00:00Commented Apr 26, 2014 at 0:58
-
No, I meant T(5) = (2/5)*(T(0)+T(1)+T(2)+T(3)+T(4)) + 5*5, Or else consider T(3) for even more easier analysis and understand how time is being calculatedthebignoob– thebignoob2014-04-26 01:05:31 +00:00Commented Apr 26, 2014 at 1:05
|
Show 1 more comment
1 Answer
A way to get rid of sums is to compute differences, after multiplying by $n$ (allow me to write LaTeX, even if this site doesn't use it; I hope the formulas are understandable):
$$ (n + 1) a_{n + 1} - n a_n = 2 a_n + 5 $$
$$ (n + 1) a_{n + 1} - (n + 2) a_n = 5 $$
This is a linear recurrence of the first order. A recurrence of the form:
$$ x_n - u_{n - 1} x_{n - 1} = f_n $$
can be reduced to a sum by dividing by the summing factor $S_n = \prod_{0 \le k \le n} u_n$ to get:
$$ \frac{x_n}{S_n} - \frac{x_{n - 1}}{S_{n - 1}} = \frac{f_n}{S_n} $$
Summing over $1 \le n \le N$ gives a solution to the equation.
In your particular case $S_n = \prod_{0 \le k \le n} \frac{n + 2}{n + 1} = n + 1$, so that:
$$ \frac{a_{k + 1}}{k + 2} - \frac{a_k}{k + 1} = \frac{5}{(k + 1) (k + 2)} $$
\begin{align} \frac{a_n}{n + 1} - \frac{a_0}{1} &= 5 \sum_{0 \le k < n} \frac{1}{(k + 1) (k + 2} \ &= - 5 \sum_{0 \le k < n} \left( \frac{1}{k + 2} - \frac{1}{k + 1} \right) \ &= - 5 \left( \frac{1}{n + 1} - 1 \right) \ &= 5 \frac{n}{n + 1} \end{align}
Finally:
$$ a_n = a_0 (n + 1) + 5 n $$
