Let $A$ be a set of generators of $S_n$, or of a doubly transitive subgroup of $S_n$. Assume $e\in A$, $A=A^{-1}$. What is the least $k$ such that $A^k$ is doubly transitive as a set? That is, what is the least $k$ such that there is a pair $x = (i,j)$, $i,j\in \{1,\dotsc,n\}$, $i\ne j$, for which $A^k x$ is the set of all pairs of distinct elements of $\{1,2,\dotsc, n\}$?

The bound $k = O(n^2)$ is very easy. Can we prove $k = O(n \log n)$? $k = O(n)$? As a starting exercise, can we at least prove $k = O(n^{3/2})$?

Alternatively, can one construct a counterexample to $k=O(n)$? (Note the classical example $A = \{(1 2), (1 2 \dotsc n)\}$ is not a counterexample.)