Prove $ \ f(n) = \frac{((log_2(n))^2 + log_2(n)}{2} = \Theta(?)$

Question

Question:

Prove $ \ f(n) = \frac{((log_2(n))^2 + log_2(n)}{2} = \Theta(?)$

My attempt:

We first prove the big oh bound.

$ \ f(n) = \frac{((log_2(n))^2 + log_2(n)}{2} \le (log_2(n))^2 + log_2(n) \le (log_2(n))^2 + (log_2(n))^2 = 2(log_2(n))^2.$

We choose $c=2$ and $ n_0 = 1$ to complete the proof.

We now prove the omega bound.

$ \ f(n) = \frac{((log_2(n))^2 + log_2(n)}{2} \ge \frac{(log_2(n))^2}{2}$.

We choose $c= \frac{1}{2}$ and $ n_0 = 1$ to complete the proof

Hence $f(n) = \Theta((log_2(n))^2)$

Answer 1

Your work is correct, anyway note that $g(n)\to \alpha>0$ then $g(n)=\Theta(1)$

[ because for $n>n_0$ and $\epsilon=\frac\alpha 2$ we have $\alpha-\varepsilon<g(n)<\alpha+\varepsilon\iff \frac{\alpha}2\times 1<g(n)<\frac{3\alpha}2\times 1$ ]

So to simplify your study, just divide $f$ by its main factor and conclude directly

$\dfrac{f(n)}{\log_2(n)^2}=\frac 12+\underbrace{\frac 1{2\log_2(n)}}_{\to 0}\to \frac 12$

Thus $f(n)=\Theta(\log_2(n)^2)$