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

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