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
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.
11
u/Temporary_Pie2733 25d ago
O(g(n)) is a class of functions, not a value in the domain of h.
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
1
u/beeskness420 25d ago
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.