I don't follow your formulation. You say "To determine the function I such that m(a(k))=b(I(k)) for all k, it will take Θ(nlogn) queries against O in the worst case"
However, you use I in the definition of the function I. Is I a recursive function? Also what is m in your definition of I?