Question

Question 6 (25 Points): asymptotic scaling of functions (O1, O2) a) Prove the following statements. (10 Points) i) f(n)=log2 (log2n) is O(0.1⋅log2n). ii) f(n)=ln(n!+n^n) is Ω(nlnn).

Answer 1

The provided statements are proved by understanding the properties and growth rates of logarithms and exponential functions, utilizing Stirling's approximation and the comparison between the growth rates of f(n) and the given bound functions.

Step-by-step explanation:

To prove the given statements, we must understand the concepts of logarithms and exponents:

1. f(n) = log2(log2n) is O(0.1⋅log2n): Since the logarithm of a number is less than the number itself, log2n grows faster than log2(log2n). Multiplying log2n by 0.1 creates a function 0.1⋅log2n, which grows slower than log2n but still faster than log2(log2n), confirming it is an upper bound for f(n).
2. f(n) = ln(n! + n^n) is Ω(nlnn): Considering n! is less than n^n for large n, the dominant term is n^n. Using Stirling's approximation (n! ≈ ∞n ⋅ (n/e)^n), ln(n!) is approximately nlnn, making ln(n! + n^n) at least asymptotically of the same order as nlnn, which shows f(n) is Ω(nlnn).