  In 1977, Strassen invented a famous baby-step/giant-step algorithm that
computes the factorial $N!$ in arithmetic complexity quasi-linear in
$\sqrt{N}$. In 1988, the Chudnovsky brothers generalized Strassen's algorithm
to the computation of the $N$-th term of any holonomic sequence in essentially
the same arithmetic complexity. We design $q$-analogues of these algorithms. We
first extend Strassen's algorithm to the computation of the $q$-factorial of
$N$, then Chudnovskys' algorithm to the computation of the $N$-th term of any
$q$-holonomic sequence. Both algorithms work in arithmetic complexity
quasi-linear in $\sqrt{N}$; surprisingly, they are simpler than their analogues
in the holonomic case. We provide a detailed cost analysis, in both arithmetic
and bit complexity models. Moreover, we describe various algorithmic
consequences, including the acceleration of polynomial and rational solving of
linear $q$-differential equations, and the fast evaluation of large classes of
polynomials, including a family recently considered by Nogneng and Schost.
