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!
No comments:
Post a Comment