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.
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: .
Thus we can combine the two to get: