Proving function

Solution 1:

From the last step you get $2^n<C$ for $n\ge k$. Put $n=\max\{\log_2C+1,k\}$ to get a contradiction.

Solution 2:

You can prove that $f(n) \notin O(g(n))$ by saying that $f(n) \in \omega(g(n))$.

To do this we will have to find $\omega$ by using its definition which is stated as: $\omega(g(n))$ is found when $C >0, \exists k, k\ge 1$ such that $0 \le f(n) > C \cdot g(n), \forall n \ge k$. In English we need to show all of $C$ and $k$ are not in $O(g(n))$.

We can do this by the following:

$f(n) < C \cdot g(n) \space \forall n \ge k \\ 4^n + 5 n^2\cdot \log n > C \cdot 2^n \space \forall n \ge k\\ \text{We see that there is an inequality so we can say,} \\ 4^n + 5n^2\log n > 4^n + 5n^2 > 4^n > C\cdot 2^n \\ \text{Then, } 4^n > C \cdot 2^n \to 2^n > C \to \log_2(2^n) > \log_2(C) \to n > \log_2(C) \\ \text{We have shown that we have a $n$ and now we will choose a k that will be greater than our $C$.} \\ \text{Say, } k = \log_2(C)+1, \text{then } n > \log_2(C) \space \forall n \ge \log_2(C) +1 \\ \therefore 4^n + 5n^2 \cdot \log n \in \omega(2^n) \text{ meaning } 4^n + 5^n \cdot \log n \notin O(2^n).$