  Computing the complexity of Markov bases is an extremely challenging problem;
no formula is known in general and there are very few classes of toric ideals
for which the Markov complexity has been computed. A monomial curve $C$ in
$\mathbb{A}^3$ has Markov complexity $m(C)$ two or three. Two if the monomial
curve is complete intersection and three otherwise. Our main result shows that
there is no $d\in \mathbb{N}$ such that $m(C)\leq d$ for all monomial curves
$C$ in $\mathbb{A}^4$. The same result is true even if we restrict to complete
intersections. We extend this result to all monomial curves in $\mathbb{A}^n,
n\geq 4$.
