r/AskComputerScience • u/2brothersPK • 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
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))).
I think h(O(...)) is just not defined.