<< Previous exercise (2.42) | Index | Next exercise (2.44) >>

In 2.42， every round minus 1. so it is (n!).

In 2.43， every round is n. so it is (n^n).

for `board-size=8`, (8^8)/(8!)≈416T

Not solved yet but share my thinking process:

Q(k): number of solutions of board size n * k

T(k): number of steps required to calculate Q(k)

original approach: T(k) = T(k-1) + n * Q(k-1)

T(0) = 1

louis's approach: T(k) = n * (T(k-1) + Q(k-1)) = n * T(k-1) + n * Q(k-1)

T(0) = 1

So louis's approach requires signifcantly more steps. How many more? It's tempted to say a factor of N^N due to tree recursion but it may not be the actual case.

Found this analysis for reference: https://wernerdegroot.wordpress.com/2015/08/01/sicp-exercise-2-43/

So, I arrived at the same result as @woofy and in the end I got these results:

Time complexity of Ex2.42 queens is n^4 Time complexity of Louis Reasoner's queens is n^n

So, roughly for Louis's approach time taken will be n^(n-4)T for n>4 and equal to T for n<=4. These results are confirmed by actually calculating execution time of both procedures and comparing them.

Given n is input size and k is k as defined in recursive iterations of

```
(queen-cols (- k 1))
```

original solution:

T(k) = T(k-1)*n, T(0) = 1

T(n) = n*T(n-1) + n*T(n-2) + ... + 1

T(n) = n!n

Louis's solution:

τ(k) = τ(k-1)^n, τ(0)=1

τ(k) = τ(k-1)^n + τ(n-2)^n + ... + 1

τ(k) = n^n

Comparing these solutions:

τ/T, τ=n^n, T=n!n

τ/T = n^n/n!n

τ/T = n^(n-1)/n! ≈ n^n

So, Louis's solution is n^(n-1)/n! times less efficient than the original which is exponentially worse on the order of n^n

Find the link given by @woofy helpful: https://wernerdegroot.wordpress.com/2015/08/01/sicp-exercise-2-43/

I think in all solutions here, only woofy is right and I don't know how Alyssa P. Hacker get his n^4.

Exchanging the order of the mapping in the flatmap results in

queen-colsbeing re-evaluated for every item in(enumerate-interval 1 board-size). Therefore the whole work has to be duplicatedboard-sizetimes at every recursion level. Since there are alwaysboard-sizerecursions this means that the whole work will be duplicatedbord-size^board-sizetimes.Therefore if the function would take T time to run for

board-size=8with correct ordering, with the interchanged ordering it will take (8^8)T to run.