$ f(n)=2\log(n)+\frac{n}{2} $. Find $g(n)$ so that $f(n)=O(n)$

Question

1. $ f(n)=2\log(n)+\dfrac{n}{2} $. Find $g(n)$ so that $f(n)=O(n)$.

2. $ T(n)=T(n-2)+1$, $T(1)=T(0)=1 $ Find $g(n)$ so that $T(n)=O(n)$.

It's supposed to be two simple questions but I guess that I didn’t understand the book’s explanation. Help.

Answer 1

When you want to say that $f(n) \in O(g(n))$, you have to show that:

$$\exists c \space \exists k \text{ such that } \forall n> k, f(n) \le c \cdot g(n)$$

Knowing that $\log n < n$, we can write:

$$f(n) = 2\log(n) + \dfrac{n}{2} \le 2n + \dfrac {n}{2} = \dfrac{5}{2}n$$

Good enough hint for you to try tackling the second question?