Hence the -maxdepth 3 param:

  # time find / -maxdepth 3 -perm -7 -type d -print
  /tmp
  /var/tmp

  real    0m0.034s
  user    0m0.005s
  sys     0m0.028s

This was run on a pretty anemic VPS. Might have to up the depth to 4 if it doesn't return anything, but IMO that's pretty unlikely.