Chapter 2, Building Abstractions with Data
Section - 2.2 - Hierarchical Data and the Closure Property
Exercise 2.43
For computing “queen k” there are k iterations such that in each iteration “queen k-1” is computed only once.
By swapping those lines, (queens (- k 1))
is called n(number of rows) times in one iteration.
Thus while computing “queen 8”, procedure “queen 7” is called 8 times.
Similarly while computing “queen 7”, procedure “queen 6” is called 8 times.
Suppose $T_i$ denotes the time taken in computing “queen i” for the original code.
Suppose $P_i$ denotes the time taken in computing “queen i” for the swapped version.
Thus we have:
$T_8 = T_7 + X_8$, where $X_k$ denotes the time taken in other parts of the code in the same(k-th, where k = 8) iteration.
Clearly this other part, $X_k$, apart from call to “queen k” will take same time in both versions, because code is same except the swapped line.
Thus:
$P_8 = 8 \times P_7 + X_8$
$= 8 \times ((8 \times P_6) + X_7) + X_8$
…..
$= (8^8) \times P_0 + 8^7 \times X_1 + 8^6 \times X_2 + 8^6 \times X_3 + ... + X_8$
Note that $P_0 = T_0$, both are base cases.
$= (8^8) \times T_0 + 8^7 \times X_1 + 8^7 \times X_2 + 8^7 \times X_3 + ... + X_8$
Also, we can easily see number of other instruction increases as number of queens increase, Thus $X_n \ge X_{n-1}$.
Thus we get:
$P_8 \le (8^8) \times T_0 + 8^7 \times X_8 + 8^6 \times X_8 + 8^5 \times X_8 + ... + X_8$
$= (8^8) \times T_0 + X_8 \times ( 8^7 + 8^6 + 8^5 + ... + 1)$
$\le (8^8) \times T_0 + X_8 \times 8^8$
$= (8^8) \times (T_0 + X_8)$
Thus we get: $P_8 \le (8^8) \times (T_0 + X_8)$.
Similarly, $T_8 = T_7 + X_8 = T_6 + X_7 + X_8 .... \le T_0 + X_0 + X_1 + ... X_8 \le T_0 + 8 \times X_8$.
Thus $T_8 \le T_0 + 8 \times X_8$.
Thus we can combine the two to get:
$P_8 \le 8^8 T_8$.