$ $
Reminder: “recurrence relations” are recursive functions.
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 split1(n - 1) + split1(n - 1); } }
\(T(0) = \color{red}{10}\)
\(T(n) = \color{red}{n + 10} + \color{green}{2T(n-1)}\)
Step one is to develop a recurrence.
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…