What is the fastest way of finding a complement? I am given a direct factor $N$ which is a normal subgroup of a group $G$. I want to find a complement of $N$ in $G$. The model of computation is RAM. It takes $O(n)$ time to find an inverse of one element. It takes $O(1)$ time to do the operation $a.b$, where $.$ means group operation. The size of the group is $n$ and group is given by table representation.
I tried to search on Google but did not able to find any algorithm for the above problem.

Q. What is the most efficient algorithm to find a complement of a direct factor?

 A: If $G$ is solvable, an algorithm that returns a set of representatives for the conjugacy classes of complements of a normal subgroup $N$ in $G$ is implemented in the Computer Algebra Software GAP4. 
See Chapter 39 of GAP4 documentation, in particular Section 39.11-6. The example given there is the following:
gap> g:=Group((1,2,3,4),(1,2));;
gap> ComplementClassesRepresentatives(g,Group((1,2)(3,4),(1,3)(2,4)));
[ Group([ (3,4), (2,4,3) ]) ]

The algorithm is based on the paper
F. Celler, J. Neubüser, C. R. B. Wright: Some remarks on the computation of complements and normalizers in soluble groups, Acta Appl. Math. 21, No.1-2, 57-76 (1990). ZBL0719.20010.
A: There is a polynomial time algorithm to find complement of a subgroup of given group by Cayley table representation. Please refer this paper by Neeraj Kaya and Timur Nezhmetdinov.
Also there is a stronger result by James B. Wilson, which gives a polynomial time algorithm for computing complement when the group is given by permutation representation. Refer this link for the same.
