Skip to content

SICP - Solution: Exercise 1.14 #39

Description

@MartinMihalev

First I want to say thank you for the detailed explanation of the exercise that really helped me to wrap my head around the problem. I found though a little issue with the formula $$T(n,2) = \frac{n^2-3n}5+1$$. When n=12 it results in 22.6 which is more than twice as less the correct answer 49(as seen on the image). Although math is not of my strengths I suspected that starting the summation with index of zero is somehow wrong and I ended up with the following formula:

$$T(n,2) = Ceil\left(\frac n5\right)+1+\sum_{i=1}^{Ceil(n/5)}T(n-5(i-1),2)$$

From this formula I derive two, because of the ceiling. When the amount is divisible by 5 without reminder:

$$T(n,2) = \left(\frac n5\right)+1+\sum_{i=1}^{n/5}T(n-5(i-1),2)$$ $$T(n,2) = \frac{n^2+7n}5+1$$

With reminder:

$$T(n,2) = \left(\frac n5+1\right)+1+\sum_{i=1}^{(n/5)+1}T(n-5(i-1),2)$$ $$T(n,2) = \frac{n^2+7n}5+3$$

The latter one gives as result 48,6 $$\approx$$ 49 when the amount is 12. The former one gives correctly 35 when the amount is 10. I hope that is helpful. Thank you again for sharing this valuable knowledge.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions