Imagine the states on a line. You solve the middle one first. Its optimal split divides the search space.
Now you have two subproblems: left half of states with left portion of search space, right half with right portion. Each subproblem is independent. The tree of recursive calls has depth . At each level, the search ranges don't overlap. That's why total work is linear per level.