  The conjugacy problem for a finitely generated group $G$ is the two-variable
problem of deciding for an arbitrary pair $(u,v)$ of elements of $G$, whether
or not $u$ is conjugate to $v$ in $G$. We construct examples of finitely
generated, computably presented groups such that for every element $u_0$ of
$G$, the problem of deciding if an arbitrary element is conjugate to $u_0$ is
decidable in quadratic time but the worst-case complexity of the global
conjugacy problem is arbitrary: it can be any c.e. Turing degree , can exactly
mirror the Time Hierarchy Theorem, or can be $\mathcal{NP}$-complete. Our
groups also have the property that the conjugacy problem is generically linear
time: that is, there is a linear time partial algorithm for the conjugacy
problem whose domain has density $1$, so hard instances are very rare. We also
consider the complexity relationship of the "half-conjugacy" problem to the
conjugacy problem. In the last section we discuss the extreme opposite
situation: groups with algorithmically finite conjugation.
