We study the adaptation dynamics of an initially maladapted asexual population with genotypes represented by binary sequences of length L. The population evolves in a maximally rugged fitness landscape with a large number of local optima. We find that whether the evolutionary trajectory is deterministic or stochastic depends on the effective mutational distance d(eff) up to which the population can spread in genotype space. For d(eff) = L, the deterministic quasi-species theory operates while for d(eff) < 1, the evolution is completely stochastic. Between these two limiting cases, the dynamics are described by a local quasi-species theory below a crossover time T(x) while above T(x) the population gets trapped at a local fitness peak and manages to find a better peak via either stochastic tunneling or double mutations. In the stochastic regime d(eff) < 1, we identify two subregimes associated with clonal interference and uphill adaptive walks, respectively. We argue that our findings are relevant to the interpretation of evolution experiments with microbial populations.