Depends on which method you use I assume. For geohashing, WITHIN should be best case O(1) and worst case O(n) depending on specificity you care about, where n is the number of geohash cells you need to generate to match the bounding box you care about (which is typically pretty small unless you want, like, a 1km box with 1cm granularity)

Frontloading computation into generating smart data structures give you better choices here.