Prove n! = O(n^n)
Вставка
- Опубліковано 18 гру 2016
- Prove by induction n factorial (n!) is Big Oh of n to the power of n O(n^n).
Please subscribe !
►Website: everythingcomputerscience.com/
►Support this channel on Patreon: / randerson112358
►Discrete Mathematics Workbooks:
(1) Practice Problems in Mathematics - www.amazon.com/gp/product/013...
(2)Discrete Mathematics Workbook - www.amazon.com/gp/product/013...
you deserve the world
My professor did this proof in class, but induction is kinda hard for me in general. Thanks for breaking it down and posting.
Yes, I too was very weak in using the induction method to prove things, you will get better over time the more you use it though !
Thanks for watching ;
randerson112358
I think there should be some correction :-
(k+1)! (k+1)! n! = o(n^n) instead of n! = O(n^n) (i.e. not tightest upper bound)
Well done. Very informative and helpful.
Thank you and Great job!
+Or Gat rhanks !
God bless you man!!! I was facing problem in doing that but your video is like angel from heaven.. thank you man💛
Thanks for watching Mishra!
Thank you for the video, I learned some new techniques!
Why can (k+1)k^k < (k+1)(k+1)^k just be written as (k+1)^(k+1)
Very neat explanation !! Thank you so much!! appreciate your contribution.
Thanks !
Thanks a lot for making it so easy to understand!!!
Wow, that is surprising ! Thanks for the nice comment, and I am glad this video helped you to understand how to do this.
-randerson112358
Thanks a lot sir..failed to ans this at an exm..Undrstood the concept now.. Thanks
Wonder how he got rid of the k on the left side in going from
=>(k+1)k! (k+1)!
(k+1)k! is equivalent to (k+1)! by definition. (k+1)! is (k+1)(k)(k-1)... while (k+1)k! is (k+1)[k(k-1)...] so by the associative property they must be equivalent.
THANK YOU. THANK YOU. THANK YOU!
Thanks for watching Carissa!
Thank you very much. Great job.
Thanks Juan!
But how do we know that n^n is the smallest upper bound?
Very helpful, thank you!!!!
I am glad the video helped and thanks for watching!
Thanks for the helpful prove. Please using this, can anyone help on how I could prove n^100 (to the power of 100) is Big Oh of n! (factorial)?
Why did you multiply (k+1) in both sides?
5:45 where did the k^k come from?
Is lower bound ie omega of n factorial, n?
Just because from your note k^k < (k+1)^k you are able to just plug this in to the right side of your equation? Why?
This is my question. Would like clarification.
@@laykefindley6604 by transitivity of inequalities. (k+1)k^k strictly less than (k+1)(k+1)^k implies (k+1)! strictly less than (k+1)(k+1)^k, and strictly less than implies less than or equal to. Which is how we get to 7:00
@@AZ-nu8bq don't you lose the = part? If (k+1)! could be equal to (k+1)(k)^k but it can't be equal to (k+1)(k+1)^k because it is stricly less than so you lose the
@@laykefindley6604 a
@@AZ-nu8bq no that's not correct. If you plot the inequalities x
Derive the execution time complexity in terms of the Big-O notation of the execution time function, T(n)= 2^n +4 n^3 +5n . Show your work clearly and provide the values for c and f(n) ????
nice one
sir can you solve ?
prove that log(n)=O(n) please
use Lim and the L'hopital, very easy that way
then*
Why (k+1)k! change to (k+1)! in 5:01
This is the definition of the factorial. www.quora.com/Why-is-n+1-n+1-n
k is within (k+1)!
why does (k+1)(k+1)^k turn to (k+1)^(k+1)?
That is just algebra imagine (k+1) = a, so we get
(k+1)(k+1)^k = (a)(a)^a-1 = a^(a-1+1) = a^a
Now let's plug back in (k+1) for a to get the following:
a^a = (k+1)^(k+1).
I'm sorry for asking again, but how does (a)(a)^a-1 transform to a^(a-1+1) then to a^a? Thanks
its an identity, when you have the same base and you are multiplying, in this case it is a, you can add up the exponents and keep the same base so for example 2^6 * 2^2 = 2^8
so .. can it be proven ?? asking for a friend
Your videos are ok... Very little to no explanation tho.
Hhmmm.... okay, thanks for the comment and watching all of my videos! Sorry you couldn't understand my explanations.
Hopefully you will have better luck elsewhere !
@@randerson112358 I think he was just trolling.
anyone from india