Problem 2.3 (b)

[aashay-m]

Hey there, I believe there's a correction in this part, since it doesn't account for adding (+1, -1, -1, +1) for N=4, which is a dichotomy that is covered by Negative intervals, but not positive intervals.

In this case, the growth function should be N^2 - N + 2.

This is obtained by taking the union of the positive and negative intervals, ie:

growth function = growth function of +ve intervals + growth function of negative intervals - dichotomies common to both
= 2 x (growth function of +ve intervals) - 2N (since dichotomies covered by both +ve and negative intervals require all +ve and -ve points to be grouped together, corresponding to part (a) Positive or Negative rays)
= N^2 +N + 2 - 2N
= N^2 - N + 2.

[wuyuanpei]

I think you are correct