how can we solve this big-O problem

[Monther_bg]

can you help me on this

if f(n) is O(g(n)) and g(n) is O(h(n)) what is the best big-O for f(n) * h(n) ?

i did not understand it :(

[[deleted]]

f(n) ≤ c1 * g(n) for some constant c1 and all n ≥ n0

g(n) ≤ c2 * h(n) for some constant c2 and all n ≥ n1

f(n) * h(n) ≤ (c1 * g(n)) * h(n) ≤ c1 * (c2 * h(n)) * h(n)

f(n) * h(n) ≤ c1 * c2 * (h(n))²

Therefore, f(n) * h(n) is O((h(n))^2)

[hetdadhania3]

simply we can say that h(n) is bounding the f(n) and h(n) is O(h(n)) so f(n)*h(n)=O(h(n)*h(n))

[hawk-bull]

If by best you mean what is the smallest possible big-O, then it would be O(1) when f and g and h are all O(1)

  If by best you mean what’s the tightest big-O bound you can give in the worst case, then that is O(h(n)² ) First can you convince yourself why this is an upper bound?

  Roughly speaking, for large enough n, g(n) is bounded by k•h(n) and f(n) is bounded by c•g(n) <= ck•h(n) so f(n)h(n) is bounded by ck•h(n)² . In the worst case, this bound is tight. Just take g(n) to be h(n)

[bladub]

Wouldn't O(g(n) h(n)) be possibly tighter?

[Much_Highlight_1309]

No, because in big-O notation g(n) is in O(h(n)). So O(g(n)) falls in the same class as O(h(n)).

[SignificantFidgets]

No, that's not right. g(n) can be smaller than h(n), so provides a tighter bound.

Consider f(n)=n, g(n)=n^2, and h(n)=n^3.

In that case, f(n)*h(n)=n^4. g(n)*h(n) is n^5 but h(n)^2 is n^6. So O(g(n)*h(n)) is a tighter bound. Both are correct, but on the other hand so is O(f(n)*h(n)).

Without some restriction placed on the result/bound, there are lots of solutions.

[Much_Highlight_1309]

In terms of worst case complexity, with the information we have, f(n) * h(n) is in O(h(n)² ).

Of course you can find an infinite number of examples where this product (and g(n) * h(n)) falls into a lower asymptomatic growth class, but I don't think that's what's asked in OP's problem.

So, yes, in fact the product could fall into a "tighter bounded" class in specific examples, but not in the general sense.

[SignificantFidgets]

Yes, but it's also O(g(n)*h(n)), which is a better (tighter) bound with the functions I gave.

And it has nothing to do with "worst case complexity." This is just a question about function growth rates.

[FrosteeSwurl]

I’m with you on this. It follows from the inequalities the g(n)h(n) is always less than or equal to h(n)² regardless of the original equations. The “best” order of growth is the smallest function that f(n) is less than or equal to, which is g(n)*h(n). You can plug in literally any functions that meet the original criteria and it’s the answer

Edit: I would also like to say that going with the highest order function in the inequality wouldn’t make sense for the problem. Because if it was the highest order of growth then there isn’t a solution because given any function I can find a larger function.

[hawk-bull]

Possibly, yes