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 denotes the time taken in computing “queen i” for the original code.

Suppose denotes the time taken in computing “queen i” for the swapped version.

Thus we have:

, where denotes the time taken in other parts of the code in the same(k-th, where k = 8) iteration.

Clearly this other part, , apart from call to “queen k” will take same time in both versions, because code is same except the swapped line.

Thus:



…..

Note that , both are base cases.

Also, we can easily see number of other instruction increases as number of queens increase, Thus .

Thus we get:




Thus we get: .

Similarly, .

Thus .

Thus we can combine the two to get:

.