8
$\begingroup$

I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if one can always find complexities between any other two.

Specifically, for any functions f and g with O(f) ⊂ O(g) does there always exist an h such that O(f) ⊂ O(h) ⊂ O(g)?

This isn't homework or anything. I'm just curious if anyone knows.

$\endgroup$
10
$\begingroup$

Yes: take a function in the middle, for some suitable definition of middle. You have a wide choice.

If $O(f) \subset O(g)$ (where the inclusion is strict), then $g \in O(g) \setminus O(f)$ (because if $g \in O(f)$ and $f \in O(g)$ then $\Theta(f) = \Theta(g)$). Take the geometric mean: let $h = \sqrt{f \cdot g}$ (since we're talking about complexity here, I assume the functions are positive).

Then $f \in O(h)$ and $h \in O(g)$ (if this is not immediately obvious, prove it using the definition of $O$), i.e. $O(f) \subseteq O(h) \subseteq O(g)$. If $O(f) = O(h)$ then $g = f \in O(f)$, which is not the case since we assumed $g \notin O(f)$. It remains to prove that $O(h) \ne O(g)$, and we'll have $O(f) \subset O(h) \subset (g)$.

If $O(h) = O(g)$ then $g \in O(h)$, i.e. there exists $A$ and $C \gt 0$ such that $\forall x \ge A, g(x) \le C \, h(x) = C \sqrt{f(x) g(x)}$. Then $g(x) \le C^2 f(x)$ (take the square and divide by $g(x)$; again, I assume positive functions), thus $g \in O(f)$, which goes against our initial assumption. The hypothesis $O(h) = O(g)$ leads to a contradiction, which concludes the proof.

$\endgroup$
  • $\begingroup$ Letting h be an average occurred to me as well, but I'm wondering if there's a stronger result. If f : x ↦ 0, and g : x ↦ 2x, then h would be x, but O(h) exactly equals O(g). I'm looking for an h that is weaker, where O(h) contains elements O(f) doesn't and is missing some elements from O(g). $\endgroup$ – begriffs Dec 14 '13 at 20:31
  • $\begingroup$ @user3102996 Oops, yes, you're right. The mistake was in “similarly”… The arithmetic mean grows like the larger function! The geometric mean, on the other hand, grows “exactly” in the middle. I've corrected my answer. $\endgroup$ – Gilles 'SO- stop being evil' Dec 14 '13 at 20:54
-3
$\begingroup$

this seems to be true for "well defined" functions or possible "space/time constructible" however there are known to be so-called (by some) "pathological functions" found by Blum in eg Blums Gap theorem for which it is not the case. so it seems similar to the concept of eg differentiation in calculus which works for "most well behaved functions" but which "pathological exceptions" have been found. there does not seem to be much systematic/further study so far of these "pathological exceptions" in complexity theory.

$\endgroup$
  • $\begingroup$ ps iirc it was oded goldreich who calls them "pathological" growth functions... maybe some would rather sweep them under the rug =( $\endgroup$ – vzn Dec 18 '13 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.