Determining the optimal variable ordering is very difficult (NP-complete), so that we just use heuristics. I have used the sifting heuristic described in the course to determine the very good variable ordering for the mentioned BDD. That reduces the overall work a lot as you can see, and that holds also when you make the case distinctions of the BDD to determine all transitions. In general, determining an optimal variable ordering is however not that easy, so you have to make an "educated guess".
