5 years later this is still a great explanation, I always understood the basics of it but when it came to proofs I always got stumpted on how to prove it. thanks alot
THANK U SO MUCH! You don't know how much you have made me happy when I finally understood it. Best explanation I've heard, very detailed and very easy to understand. This is something that seems and that people tell us is harder than it is!
This mans in god sent! My prof just gave us notes and expected us to undertand. Been looking around everywhere for an explantion on Big O but you my friend had cleared all my doubts in under 10 mins! Thanks!
Your videos are the best videos on discrete math, on RUclips. What a legend !!!!! Please continue posting as many videos on Computer Science as you can! THANKSSSSSSS
Thank you for this! Best explanation that goes step by step AND gives reasoning for each step. Choosing k = 1 makes this a whole lot easier to process and makes this very repeatable for variations of this type of problem. Gave a like!
No updates in 2 years? Pls release more videos, and charge if you must, but bring them out, students such as myself will gladly pay for real working examples of these hard to grasp concepts! Thanks
hmm the book were using in my college class just says to use 2 rules remove all the constants (5 +n becomes O(n)) and use only the highest order (so like x + x^2 becomes O(x^2)). However, this is a programming course so that could be why but this video still did help
why don't more instructors highlight the fact that you don't need to have a specfic one solution for prooving big O. this has been confusing me for few weeks until now. Thank you so much.
Your videos are great! one question though, why can't x be equal or greater than 1 at around the 8:00 minute mark? Thank you and sorry for the very late comment
im following with k=1 but the book i have then uses k=2 as an example and im completley lost. the example was is x^2 + 2x + 1 O(x^2). So for k=1, the solution was 4x^2 which i can get using your method. but for k=2, the solution was 3x^2 and i can't figure that part out.
@5:13 -- The lecturer should really have kept things consistent, especially for a beginner like myself. There really is no reason "when x >5" should have been specified when " x = 5 " was initially used. @5:24 - This is the point when you should have used " when x >5" because it is at this exact point when we're going to be experimenting with different values for "x" so the viewer/student can see what happens when we change the value of "x" --- The "What if" scenarios. My other suggestion would to have been to actually plug ever growing larger values into x and calculate the final values for those who are visual learners. x = 6, x = 10, x = 200, x = 2500, x = 100000000, etc which is "when x>5" finally makes conceptual sense. "When x>5" doesn't make sense in the "equation" written @5:13.
I appreciate the feedback. I tried to make it clear that this first example was done by exploration to illustrate the concept. The basic idea is that once x > k we need the inequality to hold. For this particular example, it was easy for me to find a value for k that gave us a nice C to make both sides equal. Once we get beyond this point where they are equal, the inequality holds. I stated that the following examples use a much easier strategy. Sure, maybe I should have added more examples for the exploration, but I am trying to keep the length of the videos down and focus on the strategy to find the C and k in the following examples. It seems like you were able to do that exploration on your own which is great!
@@discretemathvideos204 .... Appreciate the reply. Rest assure that it’s not limited to one youtube teaching channel. I’ve seen various youtubers doing the same regardless of subject matter. Often for beginners, tutorials having consistency makes a difference. Inconsistencies may cause confusion. Slow vs quick learners. Bart vs Lisa Simpsons of the world. Certain learners appreciate shorter videos, however, there are also a subset that prefer videos that are just a tad longer, with a couple more examples to truly hammer home concepts and the applications of those concept. Finding the right balance is certainly an art. I would rather see vids be a bit more thorough even if that adds one or two additional minutes - especially when they’re tutorials (as opposed to topic cliff notes). Specifically for ‘when x =5’ versus ‘when x > 5’, I decided to scroll through the comment section to see if someone may have offered clarification. Regardless, nice video. I got something out of it.
@@haneulkim4902 seriously wtf, this one thing has me so confused! the definition says x must be greater than k, but he set k to 5 when x was 5! i don't get it!
Ok lemme try to explain based on my knowledge. Let it be known that k is the "base case" of the possible values of input size n (the closest minimum value that satisfies the inequality). To perform what's on the left-hand side of the inequality (f(n)), we had to pick some value for n, which in this case is 5. We performed the left-hand expression and come up with the result of 100. Now we have to find a constant that would make the inequality true (i.e. to make 100
Sorry, I hadn't seen all of these comments earlier! The first example is just sort of done by exploration and it turned out that x = 5 gave us some nice numbers. The point is that once the functions become equal at x = 5, once we go beyond that (x > k, where k=5) we know the inequality will hold. I mention that later, there's a much simpler way to do this, but wanted to get the concept across first.
so the whole strategy to prove this, is to turn every term to the highest degree in the polynom, while x > 1 and then look for c and k. After that you are done with the prove, right?
Sorry I hadn't seen these comments earlier! This is just an exploration where it turns out that x = 5 gives us a nice C = 4 to make both sides equal. Then we can see that once x > 5, the inequality holds, so that makes the k = 5. After that, I show a much simpler way to do this. I tried to state that before this first example, but it seems some people missed that or got hung up on this example.
the whole strategy here is to find a C value to make the inequality hold. The easiest way to do that is to bump every term up to the highest degree and simply combine like terms. Then the C is right therw!
Sorry I hadn't seen these comments earlier! All you have to do is find a C and k for which the inequality holds. this technique does that in a quick and simple way. There is nothing incorrect in any of the statements.
That first example is really just done by exploration to explain the concept. I happened to notice that x=5 gave us a nice value for C. But the following examples show a much simpler strategy, so don't get hung up on where the 5 came from. It was just a value I knew would work well because I created the problem.
Sorry I hadn't seen these comments earlier! I'm not sure where you are referring to. But there is no unique k or C value, you just have to find a pair that works.
but what is g(x) in relation to f(x)? I understand that f(x) i some arbitrary function, but it doesnt make sense to describe a function in relation to another function that we do not know either???
How do you decide that g(x) is going to be 5^2 in the example? I dont understand how you chose that value, could you explain it? I think it would help me understand this a lot better.
My left ear truly enjoyed this thorough explanation
I learned more in 10 minutes, than my 3 hour lecture yesterday!!! Thanks
Thanks! Glad it was helpful
been stuck on this for 4 days now and you just cleared up my problem, your a life saver!
Thanks for the feedback and glad it helped!
So glad I learn more from youtube than a class I'm paying $1200 for.....thanks for the video, this helped tremendously!
Same and learning online is shit too
5 years later this is still a great explanation, I always understood the basics of it but when it came to proofs I always got stumpted on how to prove it. thanks alot
my left ear liked the video
THANK U SO MUCH! You don't know how much you have made me happy when I finally understood it. Best explanation I've heard, very detailed and very easy to understand. This is something that seems and that people tell us is harder than it is!
This mans in god sent! My prof just gave us notes and expected us to undertand. Been looking around everywhere for an explantion on Big O but you my friend had cleared all my doubts in under 10 mins! Thanks!
One min into your tutorial, i give you thumbs up because of paying attention to details
Your videos are the best videos on discrete math, on RUclips. What a legend !!!!! Please continue posting as many videos on Computer Science as you can! THANKSSSSSSS
Thank you for this! Best explanation that goes step by step AND gives reasoning for each step. Choosing k = 1 makes this a whole lot easier to process and makes this very repeatable for variations of this type of problem. Gave a like!
Thank you very much. I didn't listen during the 1hr lecture and I've got it all here in 10 mins. Thanks again
10 mins of this literally increased my study efficiency
My right ear understood all of this. Thank u
i learned more from this video in 5 minutes than other videos that were hours long.
Been struggling with this notation till I stumbled upon this video. Thanks !
Thank you!!! This video helped what my professor couldn’t do in hours of lecture
You explain things so well! Keep up the good work!
YOU ARE THE BEST! thank you so much!!!!! I was struggling with this for my test and you cleared up a lot of confusion.
You're a lifesaver dude, keep up the good work!!
This helped a lot! I can actually understand what you are saying unlike my thick accented teacher
I'm 30 seconds in and I allready know this video is going to help explain alot of misunderstandings I've had trying to grasp big-O notation.
do you know why he labeled x =5 as k?
Thank you from Brazil. It help me a lot!
great explanation. the simplicity of the explanation is wonderful.
Fantastic! Thanks, that made way more sense than my professor's explanation did :)
Great video. Only thing is that I had to watch it twice, switching earbuds halfway through so both my ears could hear.
No updates in 2 years? Pls release more videos, and charge if you must, but bring them out, students such as myself will gladly pay for real working examples of these hard to grasp concepts!
Thanks
Makes so much more sense than my lectures. Thank you
your video's so helpful for cs students thanks a lot
Amazing video! Clear, concise, to the point! Thanks!
sooooooo incredibly helpful! Thank you, angel!
my left ear really enjoys this
hmm the book were using in my college class just says to use 2 rules remove all the constants (5 +n becomes O(n)) and use only the highest order (so like x + x^2 becomes O(x^2)). However, this is a programming course so that could be why but this video still did help
Oh my GOD I love you. Thank you Sir!. Hope u r doing well
My left ear loved this
Thank you! It was very clear and helpful!
why don't more instructors highlight the fact that you don't need to have a specfic one solution for prooving big O. this has been confusing me for few weeks until now. Thank you so much.
Very Well Explained. Thank You Very Much.
You're welcome! Thanks for the positive feedback.
Your videos are great! one question though, why can't x be equal or greater than 1 at around the 8:00 minute mark? Thank you and sorry for the very late comment
It helps a lot a lot.... Thank you!
Very clear explanation. Thank you.
im following with k=1 but the book i have then uses k=2 as an example and im completley lost. the example was is x^2 + 2x + 1 O(x^2). So for k=1, the solution was 4x^2 which i can get using your method. but for k=2, the solution was 3x^2 and i can't figure that part out.
Thank you so much! I actually understand the concept now :)
Great video! Is it necessary to use the second approach? Would it be sufficient to only use the first approach when proving?
@5:13 -- The lecturer should really have kept things consistent, especially for a beginner like myself. There really is no reason "when x >5" should have been specified when " x = 5 " was initially used.
@5:24 - This is the point when you should have used " when x >5" because it is at this exact point when we're going to be experimenting with different values for "x" so the viewer/student can see what happens when we change the value of "x" --- The "What if" scenarios. My other suggestion would to have been to actually plug ever growing larger values into x and calculate the final values for those who are visual learners.
x = 6, x = 10, x = 200, x = 2500, x = 100000000, etc which is "when x>5" finally makes conceptual sense. "When x>5" doesn't make sense in the "equation" written @5:13.
I appreciate the feedback. I tried to make it clear that this first example was done by exploration to illustrate the concept. The basic idea is that once x > k we need the inequality to hold. For this particular example, it was easy for me to find a value for k that gave us a nice C to make both sides equal. Once we get beyond this point where they are equal, the inequality holds. I stated that the following examples use a much easier strategy.
Sure, maybe I should have added more examples for the exploration, but I am trying to keep the length of the videos down and focus on the strategy to find the C and k in the following examples. It seems like you were able to do that exploration on your own which is great!
@@discretemathvideos204 .... Appreciate the reply. Rest assure that it’s not limited to one youtube teaching channel. I’ve seen various youtubers doing the same regardless of subject matter. Often for beginners, tutorials having consistency makes a difference. Inconsistencies may cause confusion.
Slow vs quick learners. Bart vs Lisa Simpsons of the world. Certain learners appreciate shorter videos, however, there are also a subset that prefer videos that are just a tad longer, with a couple more examples to truly hammer home concepts and the applications of those concept. Finding the right balance is certainly an art. I would rather see vids be a bit more thorough even if that adds one or two additional minutes - especially when they’re tutorials (as opposed to topic cliff notes).
Specifically for ‘when x =5’ versus ‘when x > 5’, I decided to scroll through the comment section to see if someone may have offered clarification.
Regardless, nice video. I got something out of it.
Wow great video.
I learned more in 10 minutes, than my 3 hour lecture
Why is k = 5 when you said x =5 and x has to be greater than k?
have the same question, did u find the answer?
@@haneulkim4902 seriously wtf, this one thing has me so confused! the definition says x must be greater than k, but he set k to 5 when x was 5! i don't get it!
Ok lemme try to explain based on my knowledge. Let it be known that k is the "base case" of the possible values of input size n (the closest minimum value that satisfies the inequality). To perform what's on the left-hand side of the inequality (f(n)), we had to pick some value for n, which in this case is 5. We performed the left-hand expression and come up with the result of 100. Now we have to find a constant that would make the inequality true (i.e. to make 100
Sorry, I hadn't seen all of these comments earlier! The first example is just sort of done by exploration and it turned out that x = 5 gave us some nice numbers. The point is that once the functions become equal at x = 5, once we go beyond that (x > k, where k=5) we know the inequality will hold. I mention that later, there's a much simpler way to do this, but wanted to get the concept across first.
so the whole strategy to prove this, is to turn every term to the highest degree in the polynom, while x > 1 and then look for c and k. After that you are done with the prove, right?
very good explanation!
when 28x^2 is bigger than 3x^2 + 25 our O(x) = x^2, we can forget the 3 and the 25, since they are constants, right?
This is amazing, thank you!
Thank you very much teacher!
A little bit confused that why you plug in value for x directly? Shouldn't we need to do 3x^2+25
Nevermind, I figured it out. But, still confused about x= 5 is k.
Sorry I hadn't seen these comments earlier! This is just an exploration where it turns out that x = 5 gives us a nice C = 4 to make both sides equal. Then we can see that once x > 5, the inequality holds, so that makes the k = 5. After that, I show a much simpler way to do this. I tried to state that before this first example, but it seems some people missed that or got hung up on this example.
Great explanation!!
thanks! glad it helped.
Why was 25 converted to an x^2 function at around 7:03?
the whole strategy here is to find a C value to make the inequality hold. The easiest way to do that is to bump every term up to the highest degree and simply combine like terms. Then the C is right therw!
Awesome video, thank you so much
So my big thing is how can you justify a proof by simply bumping the right side up to be greater in value than it would be previously.
Sorry I hadn't seen these comments earlier! All you have to do is find a C and k for which the inequality holds. this technique does that in a quick and simple way. There is nothing incorrect in any of the statements.
so when you do the method of changing every variable to the highest degree, will k always be > 1 ( x > 1)?
Are C and k assumed to be positive integers?
Thanks a bunch!
We can take a lim both sides and C shows itself easily, without testing numbers.
could you perhaps normalize the sound on this video? the volume is very low
THANKYOU ❤️
Thanks ❤️😌
Quite helpful
THANK YOU!: D
Thank you
Awesome thanks a lot
Hold up is this Casually Explained's burner account?
bless ur soul
how to solve this kind of big-oh?
show that (x^2-1)/(x-1) is o(x)
tnx
Think about how that function you gave simplifies or use long division to simplify it.
Why did we say x = 5?
Hi sir,Could you explain how to get x=5?
That first example is really just done by exploration to explain the concept. I happened to notice that x=5 gave us a nice value for C. But the following examples show a much simpler strategy, so don't get hung up on where the 5 came from. It was just a value I knew would work well because I created the problem.
what u got against my right ear
my left ear thanks you
You must come and give lectures instead of our prof :)
Can I take x=3 ?
Sorry I hadn't seen these comments earlier! I'm not sure where you are referring to. But there is no unique k or C value, you just have to find a pair that works.
THANK YOU!
You're welcome, glad it helped!
but what is g(x) in relation to f(x)?
I understand that f(x) i some arbitrary function, but it doesnt make sense to describe a function in relation to another function that we do not know either???
the idea is that you are given the function f(x) and trying to say it is on the order of g(x). g(x) becomes a simple upper bound on f(x)
thx man
your sound is familiar , u sound like the guy from trevtutor
3x^2 + 25/x2
thanks for the explanation
YOOOOOOOOOOOOOOOOOOOOOO
horrible lecture
How do you decide that g(x) is going to be 5^2 in the example? I dont understand how you chose that value, could you explain it? I think it would help me understand this a lot better.
Is it because x^2 is the highest order in the function, and x = 5?
I believe he picked 5 as a arbitrary number to make it easier to pick c and k