In this paper, we investigate the complexity of computing the minimal faithful permutation degree for groups without abelian normal subgroups (a.k.a. Fitting-free groups). When our groups are given as quotients of permutation groups, we establish that this problem is in \(\textsf {P}\) . Furthermore, in the setting of permutation groups, we obtain an upper bound of \(\textsf {NC}\) for this problem. This improves upon the work of Das and Thakkar (STOC 2024), who established a Las Vegas polynomial-time algorithm for this class in the setting of permutation groups.