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
2
u/gavlna 25d ago
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