Since T needs to be computed for all values of t + − M ≤ t − < t + , we need to compute O(|x|M ) many values, each of which requires an optimization over M possible values.
storage requirements are O(|x|M ), whereas the computation scales with O(|x|M 2 ).