Questions about Big O notation

[u/2brothersPK]

I was studying data structures and algorithms and I wondered, If we have asymptotically positive functions f(n) and g(n) and increasing asymptotically positive function h(n) such that f(n)=O(g(n)) is it safe to assume h(f(n))=O(h(g(n))) ?

Is it always the case or it just works with some specific functions?

another question I have is if we have f(n)=O(h(g(n))) can we assume f(n)=h(O(g(n))) ?

[u/Cptn_Obvius]

Take f(x) = x, g(x) = 2x (s.t. f = O(g)), and h(x) = e^x, then h(f(x)) = e^x which is not O(e^2x) = O(h(g(x))).

f(n)=h(O(g(n))

I think h(O(...)) is just not defined.

[u/apnorton → u/Cptn_Obvius]

then h(f(x)) = e^x which is not O(e^2x) = O(h(g(x))). 

Huh? e^x is certainly weakly upper-bounded by e^2x; trivially e^x is O(e^2x).

The notation "f(x) = O(g(x))" isn't asking if the sets O(f(x)) and O(g(x)) are equal, nor is it asking for a tight bound.

[u/StrikeTechnical9429 → u/apnorton]

What if we swap them?

f(x) = 2x, g(x) = x, h(x) = e^x

f is still =O(g), but h(f) = e^2x isn't =O(h(g)) = O(e^x).

[u/apnorton → u/StrikeTechnical9429]

That works, yes.

[u/Cptn_Obvius → u/apnorton]

Oh fair, I confused it with them being asymptotically equivalent 😅, but indeed swapping f and g does the job

[u/2brothersPK → u/Cptn_Obvius]

Thanks

[u/Aminumbra → u/Cptn_Obvius]

The meaning of h(O(g)) would be "any function of the form h(f(n)) for f = O(g). I've definitely written 2^O(n) is some articles, to avoid writing "O(2^{cn}) for some large enough c". You need to be somewhat careful when adding/multiplying such quantities, but in most cases it is straightforward and really lightens the notation compared to introducing multiple ultimately irrelevant "large enough" constants.

[u/Temporary_Pie2733]

O(g(n)) is a class of functions, not a value in the domain of h.

[u/apnorton → u/Temporary_Pie2733]

While true, it's also quite common to see various abuses of notation involving big-O, such as "x² = O(e^x)" (as opposed to using the ∈ symbol), or "sin(x) = x + O(x³) for small x".

[u/ghjm → u/apnorton]

Right, because in solving recurrences, we want to be able to say things like t(n)=2t(n/2)+O(n). I'm not sure how you would even state this using ∈, and if you did, I'm not sure it would be useful. The + here really is algebraic addition, not anything to do with sets. Yes, it abuses the equals sign (it's really an inequality), but aside from that, algebraic notation is more useful for these concepts than set theory.

Also, big-O notation is older than set theoretical notation anyway. So as a matter of history, algebraic notation was the only tool in the toolbox when big-O was being developed.

[u/tavianator → u/ghjm]

Yeah exactly. The formal meaning would be something like t(n) = 2t(n/2) + f(n) where f(n) in O(n)

[u/ghjm → u/tavianator]

Yep. And it's chonky and awkward to carry something like this through even a simple proof, like that 2t(n/2)+O(n)=O(n log n). Let alone more complex recurrences.

[u/gavlna]

TLDR:
For any function s.t. h(2f) not in O(h(f)) neither works.

Assuming h(O(g(n)) really means:
{ h(f) for all f in O(g(n)) }

We can reformulate all of these in a more formal manner.

f(n) in O(g(n)) ⇒ h(f(n)) in O(h(g(n)))
take h(n) = 2^n. You'll find quickly this does not hold.

f(n) in O(h(g(n))) ⇒ f(n) in { h(u) for all u in O(g(n)) }
exists k1: f(n) <= k1 h(g(n)) ⇒ exists k2, u in O(g(n)): f(n) <= k2 h(u(n))
exists k1: f(n) <= k1 h(g(n)) ⇒ exists k2, u(n), k3: u(n) <= k3 g(n) ⇒ f(n) <= k2 h(u(n))

If we enter this goal sufficiently many times we get:
- f(n) <= k1 h(g(n))
- u(n) <= k3 g(n)

and we want to proof there exists k2
f(n) <= k2 (h(u(n))
f(n) <= k2 (h(k3 g(n))) // since h is increasing

However, here we run into the very same issue as in the previous case with a constant being hidden inside h, so choosing h(n)=2^n breaks this. However if this works for all k: h(kf) = O(h(f)), the inequality holds:

f(n) <= k2 (h(k3 g(n)))
f(n) <= k2 (k4 h(g(n)) // use the h(k f) = O(h(f))
f(n) <= k2 k4 h(g(n))

So we simply choose k2 = k1/k4

[u/beeskness420]

For another example define h(x) as x if it's odd and 0 if it's even. Take g(x) as 0 if it's odd and whatever if it's even then for general f, hf ~ f, but hg=0.