Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group.
Model of computation is RAM
For all pair of $a$ and $b$ in $G$ just check $a.b - b.a = 0$ , but it is going to take much time $O(n^2)$. Is there a faster algorithm to solve this problem?
Based on the following snippet from https://en.wikipedia.org/wiki/Quotient_group:
In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup.
It seems that you can simply set $H$ to be the identity element of $G/H$ (taking O(1) time), and then for each element $g \in G$ that has not yet been assigned to any coset, calculate the (say, left) coset of $H$ w.r.t. $g$ explicitly: $\{gh : h \in H\}$, and assign all such elements $gh$ (not just the $g$ we started with) to this coset. Calculating the coset for a particular $g$ takes $O(|H|)$ time, but the entire second phase takes only $O(n)$ time overall, since we only consider elements $g \in G$ that have not yet been assigned to a coset -- this is allowed because (according to that page) the cosets form an equivalence class, meaning no element can appear in two different cosets.
