There is a remarkable interest in the study of out-of-time ordered correlators (OTOCs) that goes from many-body theory and high-energy physics to quantum chaos. In the latter case there is a special focus on the comparison with the traditional measures of quantum complexity such as the spectral statistics. The exponential growth has been verified for many paradigmatic maps and systems. However, less is known for multipartite cases. On the other hand, the recently introduced Wigner separability entropy (WSE) and its classical counterpart provide a complexity measure that treats equally quantum and classical distributions in phase space. We compare the behavior of these measures in a system consisting of two coupled and perturbed cat maps with different dynamics: double hyperbolic, double elliptic, and mixed. In all cases, we find that the OTOCs and the WSE have essentially the same behavior, providing a complete characterization in generic bipartite systems and at the same time revealing them as very good measures of quantum complexity for phase-space distributions. Moreover, we establish a relation between both quantities by means of a recently proven theorem linking the second Rényi entropy and OTOCs.