Out of all the explanations I've watched, forums I've read, text I've banged my head against for the past 4 hours, I would have to say that THIS video did the trick. Thank you! Just wish it was in stereo instead of mono ... LOL
You cannot imagine how happy I am to find your channel. Thank you so much for existing in the same timeline and the one I'm taking discrete math in. Just in time for midterm 2...
Why tf does my textbook just not directly say "bumping everything in this polynomial to the highest degree" like this guy right here... I spent half an hour trying to make sense of inequalities that basically led to this, but I had no way of knowing until now.
I’m from the UK and this is very helpful, my university lecturer is useless at giving detailed explanations and gives us hard questions to answer which include stuff he hasn’t even covered. Really annoying. You have explained all I need to know, thank you very much.
Another video with examples involving logarithms say, "Show that 5logx is O(x)" would have been great 'cause your explanations are way better than others.
Sorry I hadn't seen these comments earlier! Thanks for the positive feedback! In the course i teach, I don't go too deep into logarithms and unfortunately, that requires a different approach. Looking at a graph is a quick way to see that it doesn't take long for x to get greater than log x.
WOW! You are very talented at teaching. Bravo! Sorta disappointed that I just now found your channel. At least there are a few more weeks in the semester,
Thanks for the positive feedback! Unfortunately that isn't really covered much in the course I teach but I believe one of them is just an upper bound and the other is both the lower and upper bound so hopefully the same basic approach might work.
thats because its a constant, C won't grow with the rest of the function. If your x is 3, then your c would be 3^4 or 3^6. However since its a constant, c is going to stay the same, at 3^3 even when x is a million, and then the equality wouldn't hold. if your c was 1,000,000^4, once x hits 2,000,000 it wont hold etc since x can grow and c cant.
I hadn't realized i had all of these comments, sorry! The idea explained below by Shane is the basic idea. C has to be a constant and this inequality has to hold for all x > k. So no matter what you pick you for C, x can always get large enough to overcome that.
The idea is that x represents the size of the problem and usually 0 doesn't make sense as a problem size for an algorithm. It might be technically ok to use x=0 but we usually use a positive integer.
Sorry that I've been so behind on catching up with comments! The approach in this video is basically assuming you have a polynomial function, not a rational or otherwise. In the example you mentioned above, once x (or n) got large enough, 2/x would get very small very quickly so I think you would still consider that function O(x^2)
Sorry I hadn't seen these comments earlier! I'm not sure which part you are referring to. But there is no unique choice for C and k, so it's possible that k=1 works in the case you are referring to.
The fact I have exam at 10am and i am watching this at 3am and actually learning shows how good of a teacher he is. Thanks for posting this.
same situation even the exam time, but i am watching this at 1 am
my left ear enjoyed this video
and my right ear also did
Don't know why the right channel isn't working
@Devin Nunez Omg I thought something was wrong with my earphone :O
@@couldrain2971 I thought the same xD
you can turn on mono audio to fix it
Out of all the explanations I've watched, forums I've read, text I've banged my head against for the past 4 hours, I would have to say that THIS video did the trick. Thank you! Just wish it was in stereo instead of mono ... LOL
Glad it helped, thanks for the feedback! I assumed it was recording in stereo, but thanks for the heads up. I'll check it in the future!
I agree, I spent 3 hours in the library, the book, was like WTF? then I watched this video and I got it.
4 years later, this is still helping people, ergo ME, so thanks!
*huge sigh of relief*
amazing tricks indeed
You cannot imagine how happy I am to find your channel. Thank you so much for existing in the same timeline and the one I'm taking discrete math in. Just in time for midterm 2...
Why tf does my textbook just not directly say "bumping everything in this polynomial to the highest degree" like this guy right here... I spent half an hour trying to make sense of inequalities that basically led to this, but I had no way of knowing until now.
Can u help me, with a QSN. Why do we need to even Bump up the values? i searching for it for like hours now
I’m from the UK and this is very helpful, my university lecturer is useless at giving detailed explanations and gives us hard questions to answer which include stuff he hasn’t even covered. Really annoying. You have explained all I need to know, thank you very much.
Another video with examples involving logarithms say, "Show that 5logx is O(x)" would have been great 'cause your explanations are way better than others.
Sorry I hadn't seen these comments earlier! Thanks for the positive feedback! In the course i teach, I don't go too deep into logarithms and unfortunately, that requires a different approach. Looking at a graph is a quick way to see that it doesn't take long for x to get greater than log x.
After 20 different Big-Oh videos, I finally found the one. Tysm!
my right ear is lonely
thank you. this is the best explanation ive found for how to prove and disprove Big O.
your explanations is better than my university lecturer. Everything make sense now.. Thank you
truth , this explanation is amazing
This is why UA-cam is amazing. Thank you.
Real good job, got it first time ever, been seeing it so many times, Thank you for posting this content!!
WOW! You are very talented at teaching. Bravo! Sorta disappointed that I just now found your channel. At least there are a few more weeks in the semester,
Thank you so much from TURKEY, great explanations :)
Thanks for the positive feedback! Glad to see it's helping people all over the world!
Your explanation is the best.. Hands down.. Thank you soo much sir.
My left ear loved this
I FINALLY GET IT!!! Please please please make videos on omega and theta!
Thanks for the positive feedback! Unfortunately that isn't really covered much in the course I teach but I believe one of them is just an upper bound and the other is both the lower and upper bound so hopefully the same basic approach might work.
In the second example, why does c have to equal x. Couldn't it equal like x^4 and then x^6 would always be greater than x^3 + 5x?
thats because its a constant, C won't grow with the rest of the function. If your x is 3, then your c would be 3^4 or 3^6. However since its a constant, c is going to stay the same, at 3^3 even when x is a million, and then the equality wouldn't hold. if your c was 1,000,000^4, once x hits 2,000,000 it wont hold etc since x can grow and c cant.
I hadn't realized i had all of these comments, sorry! The idea explained below by Shane is the basic idea. C has to be a constant and this inequality has to hold for all x > k. So no matter what you pick you for C, x can always get large enough to overcome that.
You're a life saver bro!
Thanks for the positive feedback!
u are a life savior
If I get something like 7x3 + 3x2 + 23 is O(x4). So do I bump the exponents to x4 like;
7x4 + 3x4 + 23x4. Right or no??
Help
You are a lifesaver!. thank you very much!!
You're welcome! Thanks for the positive feedback.
celal ne diyon la
Thank you very much. Your video helped a lot.
Thanks for the positive feedback!
youre a god amongst men
you're the BEST!
For the fisrt example; cant it be x>0? when x = 1, l.h.s = r.h.s making l.h.s
The idea is that x represents the size of the problem and usually 0 doesn't make sense as a problem size for an algorithm. It might be technically ok to use x=0 but we usually use a positive integer.
crisp explanation, thanks
By definition C is constant. But can C takes values in terms of X ?
Thnku so mch ❤️❤️❤️it really helped me a lot!!!
thank you perfect explaining
You told us how to disprove big O. How to disprove big omega and big theta?
Thanks for this video...
Please make a video on big omega and theta
LIFE SAVER
my discrete math professor is ass! thanks for the explanation!!!!
I dont understand the 2nd example, like why are you dividing by x^3 on RHS
can you do this to every equation? plz help :(
A big help. Thanks
Thanks for the positive feedback!
What if it's a fractions?
Like this:
3x^2+24x+2/x + 1
Sorry that I've been so behind on catching up with comments! The approach in this video is basically assuming you have a polynomial function, not a rational or otherwise. In the example you mentioned above, once x (or n) got large enough, 2/x would get very small very quickly so I think you would still consider that function O(x^2)
Why cant x be greater or equal to 1 since the equality still holds?
Sorry I hadn't seen these comments earlier! I'm not sure which part you are referring to. But there is no unique choice for C and k, so it's possible that k=1 works in the case you are referring to.
sound problem
thanks sir
THANK YOU JESUS
glad it helped! thanks for the positive feedback
good because if you not that smart at least with his cheat you can get some points , not good it is still not formal proof the teacher would want
No
U just saved my discrete math final man thank u
Glad it helped, thanks for the positive feedback!
Amazing explanation, thanks for this video - bumping tricks its amazing
Great content
Thanks! I appreciate the feedback.
If I get something like 7x3 + 3x2 + 23 is O(x2). So do I bump the exponents to x2 like;
7x2 + 3x2 + 23x2. Right or no??
Help