On the complexity of discrete logarithm problem in an interval in a finite cyclic group with efficient inversion

Discrete logarithm problem in an interval in a finite group $G=\langle P\rangle$ consists in solving the equation $Q=nP$ with respect to $n\in\{-N/2,\dots,N/2\}$ for the specified $P,Q\in G$ and $0<N<|G|-1$. If the group $G$ has an inversion, which may be computed significantly faster than the group operation, then, similarly to the solution of the classical discrete logarithm, we may speed up the algorithm. In 2010, S. Galbraith and R. Ruprai proposed an algorithm solving this problem with the average complexity $(1{,}36+\text o(1))\sqrt N$ group operations in $G$ where $N\to\infty$. We show that the average complexity of the algorithm for finding the solution of the discrete logarithm problem in interval equals $(1+\varepsilon)\sqrt{\pi N/2}$ group operations.