I'm studying Big-Oh Notation in my Discrete Structures class and I've proven most of the two questions that I've been assigned, although I'm stuck at one part on each.
So far in the class, we have not learned the induction method and are not allowed using graphs, limits or slopes of tangent lines to prove things. We can only use summations and algebraic calculations. Here is what I'm stuck on:
Note: The logarithms can be expressed with any base.
- Proving $n!$ $\leq$ $n^n$ for all $n$ $\geq$ $2$
(Original question: Prove log$(n!) \in \Omega(n$log$(n))$ - I chose $c=1/2, n_0=2$)
- Proving $3n^3-n^2+43 \geq \sqrt{n}^7$ for all $n \geq 9$
(Original question: Prove $2$log$(3n^3-n^2+43)\in O($log$(n))$ - I chose $c=7, n_0=9$)
I just can't figure out how to go about proving these things without using any of the methods listed above. If anyone has any idea where I could start, I would really appreciate some guidance!
For the first one you need to note $\log n! = \sum\limits_{i=1}^n \log i$
and $\sum\limits_{i = n/2}^n\log \frac{n}{2} \leq \sum\limits_{i = n/2}^n\log i \leq \sum\limits_{i=1}^n \log i$
(probably induction lurks here somewhere)
For the second one you need to be large, i.e. $3n^3-n^2 + 43 \leq 47 n^3$ for all $n \geq 1$. And $\log 47n^3 = 3\log n + \log 47 \leq 4 \log n$ for $n \geq 6$.