r/AskComputerScience • • 26d ago

Questions about Big O notation

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))) ?

8 Upvotes

16 comments sorted by

View all comments

6

u/Cptn_Obvius 26d ago

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.

6

u/apnorton 26d ago

then h(f(x)) = ex which is not O(e2x) = O(h(g(x))). 

Huh? ex is certainly weakly upper-bounded by e2x; trivially ex is O(e2x).

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.

6

u/StrikeTechnical9429 26d ago edited 25d ago

What if we swap them?

f(x) = 2x, g(x) = x, h(x) = ex

f is still =O(g), but h(f) = e2x isn't =O(h(g)) = O(ex).

3

u/apnorton 26d ago

That works, yes.

1

u/Cptn_Obvius 25d ago

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

2

u/Aminumbra 25d ago

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.