Co-author here. If you look into the R5N paper (link in draft), you can find this term. If you assume a routing performance of O(log n) and O(sqrt (n)) number of lookups to find the value, you get O (sqrt (n) * log n) as overall complexity (last section in paper).
For the argument of the sqrt (n) itself, see the paper.
Edit 1: Quote: "Assuming that T [random path length] is chosen large enough to achieve perfect mixing, sqrt (n / (c−1)) replicas would need to be created in order for a GET request to succeed with about 50% probability according
to the birthday paradox."
Edit 2: In a world without local minima the term itself will be 1 (you only need a single lookup and will find the value with 100% probability.
In the restricted route scenario you will have to so O(sqrt(n)) lookups.