  The worst-case complexity of group-theoretic algorithms has been studied for
a long time. Generic-case complexity, or complexity on random inputs, was
introduced and studied relatively recently. In this paper, we address the
average-case time complexity of the word problem in several classes of groups
and show that it is often the case that the average-case complexity is linear
with respect to the length of an input word. The classes of groups that we
consider include groups of matrices over rationals (in particular, polycyclic
groups), some classes of solvable groups, as well as free products. Along the
way, we improve several bounds for the worst-case complexity of the word
problem in groups of matrices, in particular in nilpotent groups. For free
products, we also address the average-case complexity of the subgroup
membership problem and show that it is often linear, too. Finally, we discuss
complexity of the identity problem that has not been considered before.
