My question comes from section Example 14.9 of the book "Markov Chains and Mixing Times (2nd edition)" written by David A.Levin and Yuval Peres. Specifically, I fully understand this example, but the author asks us to show that the lower and upper bound for this process are both of order $\frac{n\log n}{4}$ if we assume $k = \frac{n}{2}$, with no hints given in the book. So I am really stuck on how to get the sharp bounds to conclude that this chain has a cutoff at $\frac{n\log n}{4}$ when $k = \frac{n}{2}$. (Remark: even though some papers related to this chain are mentioned in the book, they are too tough for beginners in this field and they usually proved much stronger and general statements, which are not really necessary for this exercise). Thanks for the help!