If the group defined by the presentation is finite, then the Todd-Coxeter procedure (it's a procedure, not an algorithm) is guaranteed to complete eventually and to tell you the order.
The fly in the ointment is that even if the order turns out to be something small, it is impossible to predict in advance how long the computation might take and how much computer memory it might require.
It is possible to write down reasonably short presentations of the trivial group (and which can be proved to define the trivial group) that would take the standard Todd-Coxeter procedure longer than the expected life of the universe to prove trivial.
Edit, July 2024. There is a question in the comments about how to prove that the Todd-Coxeter procedure is guaranteed to terminate (given enough time and memory) whenever $|G:H|$ is finite, where $H$ is a given finitely generated subgroup of the finitely presented group $G$. This property depends on the assumption that for any coset $Hg$ and any group generator $x$, the cosets $Hx$ and $Hx^{-1}$ are defined at some point. In fact some of the standard strategies used (such as HLT+Lookahead) do not satisfy this assumption a priori, so they have to be modified so that they satisfy it.
With this assumption, there is a technical proof of the property in Proposition 1.3 of Chapter 5 of the book "Computation in Finitely Presented Groups" by Charles Sims. An alternative proof can be found in Theorem 5.5 of "Handbook of Computational Group Theory" by Holt, Eick and O'Brien. This second proof says in outline that, if the procedure does not terminate, then it constructs the infinite coset table of $G$ on the cosets of $H$, contradicting the assumption that $|G:H|$ is finite. Some people are suspicious of a proof that relies on a procedure that constructs an infinite object, but (not surprisingly) I think it is OK.
The left cosets of $G$ with respect to $H$ are the subsets of $G$ of the form $gH$, with $g\in G$, whereas the right cosets are those of the from $Hg$. Now, suppose that $H$ is a normal subgroup of $G$. This means that, for each $g\in G$, $g^{-1}Hg\subset H$. Actually, since $G$ is finite, it means that $g^{-1}Hg=H$. This, in turn, is equivalent to $Hg=gH$. So, if $H$ is a normal subgroup of $G$, $\{Hg\mid g\in G\}=\{gH\mid g\in G\}$; in other words, the set of right cosets is equal to the set of left cosets. It's not hard to prove that if the set of right cosets is equal to the set of left cosets, then $H$ is a normal subgroup of $G$.
Best Answer
It is the second condition that is used.
For your example, if you want to know if $a^{3}H$ is the same coset as $aH$ you need to work out $a^{-3}a$ and check to see if it belongs to $H$. If it does the cosets will be the same and if it does not then the cosets will be different. Now $a^{-3}a$ is $a^{(-3+1)}=a^{2}$. So you need to check if $a^{2}\in H$.