@JoelDavidHamkins: I want the following statement to be true -- For every function $f(|n|)$ and for every recursive function, there exists a recursive definition that is $O(f(|n|))$ in Godel complexity if and only if there exists a Turing machine that computes the function in $O(f(|n|))$ steps. I am not restricting my attention to Turing machines of a particular notation alphabet -- If there is a recursive definition in $O(|n|)$ then I'd like some Turing machine of any input alphabet that runs in $O(|n|)$ steps.

Yes, by "best-case" I mean "optimal worst-case," thank you. By "equal to," I mean "asymptotically equal to" - I would like it such that (for example) if a function can be implemented in $O(|n|)$ time on a Turing machine, then it can necessarily be implemented in $O(|n|)$ time via primitive recursive functions (and vice versa).

Man, that is a cool answer you linked to. I do have a way to test intersections, so that will do perfectly.

1. Yes, it's the union, not the intersection of the sets (the intersection would be convex =) ). 2. Yes, I am attempting a floating-point algorithm. Rather than place restrictions on the sets, I'm hoping to use standard convex optimization techniques as a subroutine (the $\epsilon$-fudginess in these techniques is okay; I'd be fine with an algorithm that reports "the functions come within $\epsilon$ of being hole-less").