Answer: h(n) = O(f(n)); g(n) = Ω(f(n)).

## Explanation Let's analyze the asymptotic behavior of the three functions: 1. **f(n) = 2^n** - Exponential function 2. **g(n) = n!** - Factorial function 3. **h(n) = n^{log n}** - This can be rewritten using properties of logarithms ### Step 1: Compare growth rates For large n: - **n! grows faster than 2^n** (Stirling's approximation: n! ≈ √(2πn)(n/e)^n) - **n^{log n} grows slower than 2^n** for large n Let's prove this mathematically: **Comparing h(n) and f(n):** ``` h(n) = n^{log n} = (2^{log n})^{log n} = 2^{(log n)^2} f(n) = 2^n ``` For large n, n grows much faster than (log n)^2, so 2^n grows much faster than 2^{(log n)^2}. Therefore: **h(n) = O(f(n))** **Comparing g(n) and f(n):** Using Stirling's approximation: n! ≈ √(2πn)(n/e)^n For n ≥ 4, n! > 2^n (can be proven by induction) Therefore: **g(n) = Ω(f(n))** (g(n) grows at least as fast as f(n), actually much faster) ### Step 2: Check each option **A) f(n) = o(g(n)); g(n) = o(h(n))** ❌ - f(n) = o(g(n)) is TRUE (f grows slower than g) - g(n) = o(h(n)) is FALSE (actually h grows slower than g) **B) f(n) = Ω(g(n)); g(n) = O(h(n))** ❌ - f(n) = Ω(g(n)) is FALSE (f does NOT grow at least as fast as g) - g(n) = O(h(n)) is FALSE (g grows faster than h) **C) g(n) = O(f(n)); h(n) = O(f(n))** ❌ - g(n) = O(f(n)) is FALSE (g grows faster than f) - h(n) = O(f(n)) is TRUE **D) h(n) = O(f(n)); g(n) = Ω(f(n))** ✅ - h(n) = O(f(n)) is TRUE (h grows slower than f) - g(n) = Ω(f(n)) is TRUE (g grows at least as fast as f) **E) Nenhuma das anteriores** ❌ Since option D is correct, this is false. ### Conclusion Option D is correct because: 1. h(n) = n^{log n} grows slower than f(n) = 2^n 2. g(n) = n! grows faster than f(n) = 2^n

Author: Danyel Barboza