It seems illogical that a model with o(n3) variables and constraints consumes less time than a model with o(n2) variables and constraints. Could these results be explained ? or the use of multiple binary variables instead of of low variables could reduce time?
There are a number of possible explanations (not mutually exclusive). The larger model might have a tighter continuous relaxation. (You can test that by relaxing the integrality restrictions and solving both LPs.) Assuming you are using a solver that has a presolve stage, there may be something in the first model that allows the presolver to tighten things in a way it cannot do in the second model. The solver may generate cuts that are more productive in the first model than in the second (or not available / not relevant in the second). Also, there may be an element of luck involved (particularly if your time comparison is based on a single problem instance).
Integer programs are perverse beasts.