Given an input table with binary operation $\circ$. I want to check whether given input table represents a group or not.
I need to verify the four axioms of a group.
- The identity I can find it by just scanning the first row of the given table. -----$\mathcal{O}(|G|)$ running time.
- Find the closure operation ie.e for any $x,y \in G$, I need to show that $x \circ y \in G $.------$\mathcal{O}(|G|^2)$
- An inverse of an element.----$\mathcal{O}(|G|^2)$ Running time.
- Associativity operation. -----$\mathcal{O}(|G|^3)$
Which gives me a $\mathcal{O}(|G|^3)$ running time algorithm to check whether the input table corresponds to some group.
Question : What is the fastest algorithm to check whether the input table is a group?
Model of computation is RAM, which computing $x \circ y$ takes constant time.