1 is True. \Theta is transitive. 2 is True. O is transitive, and h(n)=\Omega (f(n)) is the same as f(n)=O (h(n)) 3 is False: f(n) = n and g(n) = 2n + 1.
All constants are related to each other by a constant factor, so they have
the same order of growth. f(n)=\Theta (g(n)), and therefore f(n)=O (g(n)) andf(n)=\Omega (g(n)) also.
The correct ordering of these functions is f_4(n),f_1(n),f_3(n),f_2(n). To see
why, we first use the rules of arithmetic series to derive a simpler formula for f_4(n): \begin{aligned} f_4(n)&=\sum_{i=1}^{n}(i+1) \\ &= \frac{n((n+1)+2)}{2}\\ &= \frac{n(n+3)}{2}\\ &= \Theta (n^2) \end{aligned} This is clearly asymptotically smaller than f_1(n)=n^{\sqrt{n}} . Next, we want to compare f_1(n), f_2(n) and f_3(n). To do so, we transform both f_1(n) and f_3(n) so that they
look more like f_3(n):
The exponent of the 2 in f_1(n) is a function that grows more slowly than linear time;
the exponent of the 2 in f_3(n) is a function that grows linearly with n. Therefore,
f_1(n)=O(f_3(n)). Finally, we wish to compare f_3(n) with f_2(n). Both have a linear function of n in their exponent, so it's tempting to say that they behave the
same asymptotically, but they do not. If c is any constant and g(x) is a function, then
2^{cg(x)} = (2^c)^{g(x)} . Hence, changing the constant of the function in the exponent is the
same as changing the base of the exponent, which does affect the asymptotic running
time. Hence, f_3(n) is O(f_2(n)), but f_2(n) is not O(f_3(n)).
The correct order of these functions is f_1(n),f_4(n),f_3(n),f_2(n). The variable n never appears in the formula for f_1(n), so despite the multiple exponentials, f_1(n) is constant. Hence, it is asymptotically smaller than f_4(n), which does grow with n. We may rewrite the formula for f_4(n) to bef_4(n)=n\sqrt{n}=n^{1.5}. The
value of f_3(n) = \binom{n}{2} is given by the formula \frac{n(n-1)}{2}, which is \Theta (n^2). Hence,
f_4(n)=n^{1.5}=O(n^2)=O(f_3(n)). Finally, f_2(n) is exponential, while f_3(n) is
quadratic, meaning that f_3(n) is O(f_2(n))
I think in question 2 all options are correct