2.33
The closed-form of the geometric series gives
f₃(n)=∑i=0ⁿ2ⁱ = 2n+1−1 = Θ(2ⁿ) and thus
f₄(n)=log₂(∑2ⁱ)=log₂(2n+1−1)=Θ(n).
Comparing growth rates:
1. f₄(n)=Θ(n)
2. f₂(n)=n(log n)² = Θ(n log²n) (> linear)
3. f₁(n)=n²log n = Θ(n² log n) (> quadratic)
4. f₃(n)=Θ(2ⁿ) (exponential)
Therefore the increasing asymptotic order is:
[math]f_4(n) \; \in \; o\!\big(f_2(n)\big) \; \in \; o\!\big(f_1(n)\big) \; \in \; o\!\big(f_3(n)\big)[/math],
i.e.
f₄(n) < f₂(n) < f₁(n) < f₃(n).
Back to
Chapter 2
