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
Your videos are the best videos on discrete math, on CZcams. What a legend !!!!! Please continue posting as many videos on Computer Science as you can! THANKSSSSSSS
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!
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
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.
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
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.
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
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?
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! 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.
@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.
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.
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.
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.
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.
@@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.
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???
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
my left ear liked the video
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!
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
Your videos are the best videos on discrete math, on CZcams. What a legend !!!!! Please continue posting as many videos on Computer Science as you can! THANKSSSSSSS
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!
i learned more from this video in 5 minutes than other videos that were hours long.
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!
Amazing video! Clear, concise, to the point! Thanks!
You explain things so well! Keep up the good work!
Thank you!!! This video helped what my professor couldn’t do in hours of lecture
One min into your tutorial, i give you thumbs up because of paying attention to details
Thank you very much. I didn't listen during the 1hr lecture and I've got it all here in 10 mins. Thanks again
Been struggling with this notation till I stumbled upon this video. Thanks !
You're a lifesaver dude, keep up the good work!!
Fantastic! Thanks, that made way more sense than my professor's explanation did :)
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
thank you, discrete math lord
great explanation. the simplicity of the explanation is wonderful.
YOU ARE THE BEST! thank you so much!!!!! I was struggling with this for my test and you cleared up a lot of confusion.
10 mins of this literally increased my study efficiency
😀
sooooooo incredibly helpful! Thank you, angel!
My right ear understood all of this. Thank u
Thank you from Brazil. It help me a lot!
Great video. Only thing is that I had to watch it twice, switching earbuds halfway through so both my ears could hear.
Makes so much more sense than my lectures. Thank you
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
This helped a lot! I can actually understand what you are saying unlike my thick accented teacher
Thank you! It was very clear and helpful!
Very clear explanation. Thank you.
your video's so helpful for cs students thanks a lot
This is amazing, thank you!
It helps a lot a lot.... Thank you!
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?
Awesome video, thank you so much
Thank you so much! I actually understand the concept now :)
My left ear loved this
Oh my GOD I love you. Thank you Sir!. Hope u r doing well
my left ear really enjoys this
Wow great video.
Great video! Is it necessary to use the second approach? Would it be sufficient to only use the first approach when proving?
very good explanation!
Very Well Explained. Thank You Very Much.
You're welcome! Thanks for the positive feedback.
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.
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
Thanks a bunch!
Thank you very much teacher!
Great explanation!!
thanks! glad it helped.
so when you do the method of changing every variable to the highest degree, will k always be > 1 ( x > 1)?
I learned more in 10 minutes, than my 3 hour lecture
Awesome thanks a lot
bless ur soul
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!: D
THANKYOU ❤️
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
Quite helpful
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?
Thank you
Thanks ❤️😌
THANK YOU!
You're welcome, glad it helped!
Are C and k assumed to be positive integers?
thx man
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?
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!
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.
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.
@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.
my left ear thanks you
could you perhaps normalize the sound on this video? the volume is very low
what u got against my right ear
Why did we say x = 5?
Hold up is this Casually Explained's burner account?
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.
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
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.
We can take a lim both sides and C shows itself easily, without testing numbers.
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.
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.
You must come and give lectures instead of our prof :)
your sound is familiar , u sound like the guy from trevtutor
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)
YOOOOOOOOOOOOOOOOOOOOOO
3x^2 + 25/x2
thanks for the explanation
horrible lecture
make a better one or get out buddy. this is the reason i have a degree.