0
$\begingroup$

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.

  1. 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$)

  1. 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!

$\endgroup$
2
  • $\begingroup$ Not learnt the induction method? You cannot do without it in general. Besides, the sign in the first question must probably be reversed, and for that you don't require induction : note that $\sqrt n \leq n$ for all $n \geq 2$, and $1 \leq (n-1)!$ for all $n \geq 2$ and multiply these inequalities. $\endgroup$ Mar 17, 2018 at 5:07
  • $\begingroup$ I suppose it was intended to be something like $\sqrt{n^n}$ $\endgroup$
    – dEmigOd
    Mar 17, 2018 at 5:56

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.