SICP Solutions

Section - 2.3 Symbolic Data

Exercise 2.61

Test/Output:

Sometimes, adding an element chances are that we only need to add the new element in the front of the list, thus in $\theta(1)$.

Sometimes, adding an element chances are that we need to add the new element in the end of the list, thus in $\theta(n)$.

Thus on average we have the complexity of $\theta( \frac n 2 )$.