$ $
E.g.:
\(f(n) = f(n-1) + 1\)Finding closed-form solutions requires that we provide initial conditions:
\(f(0) = 1\)
Draw a recursion trace for split(3):
Express the number of activation records as a recurrence:
\(T(0) = 1\)
\(T(n) = 1 + 2T(n - 1)\)
More typically, we want to count the number of steps executed by a recursive algorithm:
public static int split1(int n) {
for (int i = 0; i < n + 10; i++) {
//BASIC OPERATION HERE.
}
if (n == 0) {
return 1;
} else {
return split(n - 1) + split(n - 1);
}
}
\(T(0) = \color{red}{10}\)
\(T(n) = \color{red}{n + 10} + \color{green}{2T(n-1)}\)
Typically:
Initial Conditions
\(T(size\_of\_base\_case) = \#operations\_required\_for\_base\_case\)
Recurrence Relation
\(T(n) = \#operations\_in\_call + \#recursive\_calls \times T(size\_of\_calls)\)
Develop a recurrence that describes the number of multiplication operations performed by the following code block:
public static int fun(int n) {
if (n == 1) {
return 5;
} else {
int sum = 1;
for (int i = 0; i < 7; i++) {
sum *= 2;
}
return sum * fun(n - 1);
}
}
\(T(??) = ??\)
\(T(n) = ??\)
public static int fun(int n) {
if (n == 1) {
return 5;
} else {
int sum = 1;
for (int i = 0; i < 7; i++) {
sum *= 2; // Seven here.
}
return sum * fun(n - 1); // One here.
}
}
\(T(1) = \color{orange}{0}\)
\(T(n) = \color{red}{8} + \color{green}{T(n-1)}\)
Write a recurrence relation that describes the number of additions performed by this method.
Write a recurrence relation that describes the number of assignments to sum performed by this method.
Write a recurrence relation that describes the number of assignments to sum performed by this method.
public static int fun(int n) {
if (n <= 1) {
return 8;
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += fun(n - 1) + fun(n - 2);
}
return sum;
}We need two initial conditions!
\(T(0) = 0\)
\(T(1) = 0\)
\(T(n) = n + 1 + nT(n-1) + nT(n-2)\)
Next time…