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.