literally watched a dozen of video still couldn't understand the how to write it down a clear proof....You're the only person who did it .... A BIG thanks to u man... u r a life saver
The ONLY person who has just explained this and walked through it clearly is you. Thank you. I swear every single "example" (used very loosely) I've seen before this rushes through it and doesn't explain anything. Thank you for being clear and easy to follow.
I want to thank you for making this video. Proofs hit me out of nowhere and made no sense to me. This video gave me a much better understanding than anything else I found, and you've helped me find my footing because of it. Truly, thank you
Finally! I spent days trying to find something to explain this because i could not connect the info in my book. It simply showed the same function that you started with and then the conclusion. asked some math majors and EE engineers I work with, couldn't figure out how the book went from start to finish either. So thank you very much
This is fantastic. Was just staring blankly at my prof's explanation and it didn't really help me. This is the first video I found that actually made it easy to understand. This will really help me in my mid term upcoming in the next two weeks.
I've been struggling to understand what values to make n and the constant. Nice to see a clear demonstration on why you arrived at n = 4 for the proof unlike many other resources I've looked at.
At about 1:48 you say: We want to find a function bigger than this one. Why is that? Why do you replace everything that's not n^2 with n^2? What's the logic behind it? I've seen it in other problems being solved and I still don't get it. Thanks!
Raphael S Carvalho , good question, in this video I took a short cut for time and showed that (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2 for all n > 1 which is true. There was NO transforming of the original equation from (n^2 + 2n + 1) / n^2 (n^2 + 2n + 1) / n^2, it was a statement or a fact that (n^2 + 2n^2 + n^2) / n^2 is ALWAYS greater than (n^2 + 2n + 1) / n^2 whenever the value 'n' is greater than 1. You can see the value on the left hand side grows faster when you add larger and larger values for n. For EXAMPLE: let n = 10 Then the inequality equals the following by substitution: ORIGINAL inequality: (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2 After Substitution: (10^2 + 2(10^2) + 10^2) / 10^2 > (10^2 + 2(10) + 1) / 10^2 Now to simplify: (100 + 200 + 100) /100 > (100 + 20 + 1)/100 = (400)/100 > (120)/100 = 4 > 1.2 which is TRUE Now let's use a bigger number like 50: Let n = 50 Then the inequality equals the following by substitution: ORIGINAL inequality: (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2 After Substitution: (50^2 + 2(50^2) + 50^2) / 50^2 > (50^2 + 2(50) + 1) / 50^2 Now to simplify: (2500 + 5000 + 2500)/ 2500 > (2500 + 100 + 1) / 2500 = (10000)/2500 > (2601)/2500 = 4 > 1.0404 which is TRUE Notice that the value on the left always equals 4 as the value 'n' increases, and the value on the right gets smaller as the value n increases, this shows the function on the right hand side will always be less than the number 4 as long as the value n is greater than 1. NOW for your question, which I believe you meant is, how do I know that the second function (n^2 + 2n^2 + n^2) / n^2 is ALWAYS greater than (n^2 + 2n + 1) / n^2, and the simple answer is by doing an algebra proof or using intuition. The intuition and proof are below: Intuition: If I have a number (a constant) divided by a variable, the over all value of that number will always decrease, because n grows faster than a constant. A constant doesn't grow at all. For Example 1/n will always be less than or equal to 1(a constant) whenever n is greater than or equal to 1. function: 1/n let n = 1, function = 1/1 = 1 let n = 2, function = 1/2 = .5 let n = 3, function = 1/3 = .333... let n = 4, function = 1/4 = .25 so the constant value that 1/n will never be greater than is 1, whenever n is greater than or equal to 1. Hence: 1/n = 1 second example: Here I will use a denominator that grows faster then it's numerator like the above example: function: (n+1) / n^2 let n = 1, function = (1 + 1) / 1^2 = (2)/1 = 2 let n = 2, function = (2 + 1)/ 2^2 = 3/4 = .75 let n = 3, function = (3 + 1)/ 3^2 = 4/9 = .44444..... so the constant value that 1/n will never be greater than is 2, whenever n is greater than or equal to 1. Hence: (n+1)/ n^2 =1 So this means for my orignal function '(n^2 + 2n + 1) / n^2', as long as the denominator is the biggest possible value or grows the fastest there is a constant that the function will be less than, in the above cases, that constant is a 1 for example 1 and 2 for example 2. OKAY HERE IS YOUR ANSWER: By making every number in the numerator divisible by the denominator (AKA the highest possible value) we get a constant that the original function is less than. From example 1, the function 1/n will never be greater than 1 By using the above principle (making the numerator a multiple of the denominator) we can see this is true. Ex1: Original = 1/n Transformation = n*(1) / n = n/n = 1 (The constant that the function will never be greater than) Hence: n/n > 1/n whenever n > 1 Ex2: Original = (n+1)/n^2 (Notice both n and 1 grow slower than n^2) Transformation= (n^2 + n^2)/ n^2 = 2(n^2)/n^2 = 2 (The constant that the function will never be greater than) Hence: (n^2 + n^2) / n^2 > (n+1)/n^2 whenever n > 1 and so it follows to find a constant that our original function will always be less than we need to do a similar 'transformation' Ex3:Original = (n^2 + 2n + 1) / n^2 Transformation = (n^2 + 2n^2 + n^2) / n^2 = 1 + 2 + 1 = 4 So 4 is the constant that (n^2 + 2n + 1) / n^2 will always be less than whenever n > 1. Few, last proof this is always true Using the inequality:(n^2 + 2n^2 + n^2) / n^2 >= (n^2 + 2n + 1) / n^2 , and n >=1 1) Multiply both sides by n^2 to get the below: (n^2 + 2n^2 + n^2) >= (n^2 + 2n + 1) whenever n >= 1 2) Subtract n^2 from both sides to get the below: ( 2n^2 + n^2) >= (2n + 1) whenever n >= 1 3) Subtract 1 from both sides to get the below: (2n^2 + n^2 - 1) >= (2n) whenever n >= 1 4) Subtract 2n from both sides to get the below: (2n^2 + n^2 - 1 - 2n) >= 0 whenever n >=1 5) Add like terms and rearrange to get the below: (3n^2 - 2n - 1) >= 0 whenever n >= 1 6) Divide both sides by n^2 (3 - 2/n^2 - 1/n^2) > 0 , whenever n >= 1 Note: 2/n^2 is always less than or equal to 2 and 1/n^2 is always less than or equal to 1 whenever n increases since the smallest value n can be is 1 7) Rewrite the equation as the maximum values 2/n^2 and 1/n^2 can be (3 - 2 - 1) >= 0 ==> (1-1) >= 0 ==> 0 >= 0 which is always true. I hope this spreads some light on the reason why I said (n^2 + 2n^2 + n^2) / n^2 >= (n^2 + 2n + 1) / n^2 , and n >=1 randerson112358
@@dynamohack Consider a simplier example where we know that n²/n² is always ≥ to n/n² for all n ≥ 1.We can use this fact to find an upper bound that suggest that n²/n² = 1 thus 1 is always ≥ to 1/n² for all n ≥ 1. In a similar fashion (n²+2n²+n²)/n² will always be ≥ to (n²+2n+1)/n² for all n ≥ 1. By breaking (n²+2n²+n²)/n² into independent fractions we get n²/n² + 2n²/n² + n²/n² simplifies to 1+2+1=4 thus 4 is always ≥ to (n²+2n+1)/n² for all n ≥ 1.
At 2:33 you say for all n greater than 1, but then you pick 1 as your input and then say 4 is greater than the right side. Don't you have to pick a number greater than 1 for that to make sense? Try plugging in 1 to both sides of that inequality, you'll see that you get, 4 > 4, which is not true.
OOh My god! This just made things clear! Been re-reading my textbook trying to understand this concept all week. But this video helped me finally understand big-o proof in a matter of minutes. Wish I found this sooner. Thanks!
Thank you so much. I've been struggling with Big O notation and pulling my hair out trying to figure it out. Nothing has helped clear the fog. The text book just didn't make sense nor did any of the other material I've read online. This is the first video that actually made sense to me.
+saberdino966 No problem , I definitely understand your frustration. I could barely understand the material in my classes, and had to go and ask other professors, and students to give me some clarity on this subject. Keep learning this stuff and any computer science topic, it only gets better and more interesting. I really enjoy this field. randerson112358
Awesome video. This really helped clear some things up for me. I see that you have some other videos up, which is great. If I could make one request, please put your camera on a tripod or some stable surface. I'm sure that I'm a fringe case, but the slight wobble of the video is enough to make me motion sick.
But how did you know to choose k = 1? Why wasn't it k = 8, or k = 6? Or some other number? What made you choose that? Please explain your thought process.
Hi Veritas, I could've chosen k= 8 or k=6 or k= 89 or k = 100000 , as long as k is some number greater than 0. Notice that in this video if k=8 then it still satisfies the big oh definition, since I chose values of n >= 1 this implies values of n>=2 and n >= 3 and so on. So I think you may be a little confused as to what k is and why do we need it in the definition to prove big-oh. The definition of Big-Oh: A function f(n) is said to be O( g(n) ) if there exist two positive constants C and k that will make the following equation true; f(n) k The value of k replaces the input value n, in the function. For example Let f(n) = n^2 and let g(n) = n^3 Let's create a chart for the vaues of n n | f(n) | g(n) ------------------------- 0 | 0 | 0
+Kenny Worden All we had show is f(n) = k this proves f(n) is O( g(n) ) Rewrite the equation/ definition to get the below: f(n) / g(n) =k to prove f(n) is O( g(n) ) In this example : f(n) = (n^2 + 2n + 1) g(n) = (n^2) C = 4 k = 1 Notice as the value of n increases noted by n>=1, the value of f(n) /g(n) decreases. Specifically if you plug in any value for n that is greater than 1, then (n^2 + 2n + 1) / (n^2) will always be less than or equal to 4. NOTE: if you don't see this then plug in values for 'n' and you will notice that (n^2 + 2n + 1) / (n^2) will get smaller and smaller as n gets bigger. For example plug in n=1, then n=2, then n=3 and so on until you see the decreasing pattern. So since we proved the statement f(n) / g(n) =k is true, we proved f(n) is O( g(n) ). or more specifically Since we proved (n^2 + 2n + 1) / (n^2) = 1 is always TRUE , We proved (n^2 +2n + 1) is O( (n^2) randerson112358
you can solve it much easier considering the limit when n goes to infinite, right? I am still learning but I think the limit must be a constant for it to be big O
This is the best explanation of big-oh I have seen so far. Thank you very much for saving a student from committing suicide( just kidding). You are great
Hi, I am not sure during which time on the video you are referring. However we must show f(n) k So this means that we our constant can be equal to or greater than 4 whenever n>1
gotta love paying thousands of dollars to go to hours of lectures only to have to watch 3 minutes of a youtube video of a dudes whiteboard in 2014 to learn this
at 3:00 to 3:09, I think you are making a mistake here... If we are looking F(n) > f(n), then n can NOT equal 1 in this case, it doesn't make sense. for example... n = 1 (which is what you did at 3:00 (1^2 + 2(1^2) + 1^2)/1^2 > (1^2 + 2(1) + 1)/1^2 (1 + 2 + 1)/1 > (1 + 2 + 1)/1 = 4 > 4... Which is not correct for n = 1. In fact... I believe that n needs to stay n >= 1... Unless I'm missing something very fundamental here. It makes no sense to have n = 1. I think logically, what you did was correct, but stating that n should be n > 1, and then using n = 1 to prove that f(n)/g(n) >= C for all n >= 1 is a bit misleading.
Hi Felxaga , I do believe you are missing something fundamental. From your comment: "(1^2 + 2(1^2) + 1^2)/1^2 > (1^2 + 2(1) + 1)/1^2 (1 + 2 + 1)/1 > (1 + 2 + 1)/1 = 4 > 4... Which is not correct for n = 1." You are missing the '=' sign, it is supposed to be 4 >= 4, which is true, but I did not substitute 1 for n. I do not know where you are seeing n = 1, n is greater than or equal to 1. If you are confused on how I got the number 4, I used division..... [ (n^2) + 2(n^2) + (n^2) ] divided by (n^2) = 1 + 2 + 1 = 4. Lets simplify: [ (n^2) + 2(n^2) + (n^2) ] /(n^2) = (n^2)/ (n^2) + 2(n^2)/(n^2) + (n^2)/(n^2) = 1 + 2(1) + 1 = 4 I divided by n^2 to get 1, I used algebra, no substitution where n=1 This is LOGICALLY correct, plug in any number for n that is greater than 1 into the following equation and see if it's true: Equation: f(n) / g(n)
Yeah... yeah.... this is what not doing any math for several years does to you... you start missing the very fundamentals... HOW DID I MISS THIS!?!?!? Would you believe I used to tutor in advanced calculus just 3 years ago? Anyways, thanks for pointing that out for me, I need to whip my brain back into shape >.
Sorry I might have phrased my question wrongly. What I meant was do we always use n >= 1? I have seen many examples online and all uses the value 1 but I do not understand why 1.
Wow Differential Equations, that's very good ! You are correct, but so many teachers use the '=' operator and many older papers do as well, that I decided to continue using that notation as well to help others. I try to mix it up in all of my videos. But Big O is a set of functions which is why we use there exists or belongs to instead of equal. I don't know why '=' was ever used, but I do know mathematicians/teachers still use that notation today.
literally watched a dozen of video still couldn't understand the how to write it down a clear proof....You're the only person who did it .... A BIG thanks to u man... u r a life saver
Thanks Anchal, I appreciate it and I had similar troubles when I was first learning this stuff.
The ONLY person who has just explained this and walked through it clearly is you. Thank you. I swear every single "example" (used very loosely) I've seen before this rushes through it and doesn't explain anything. Thank you for being clear and easy to follow.
8 years since this video dropped and it helped me work through big O. Thank you!
I want to thank you for making this video. Proofs hit me out of nowhere and made no sense to me. This video gave me a much better understanding than anything else I found, and you've helped me find my footing because of it. Truly, thank you
Thanks for the comment Alreeshid ! I truly appreciate it !
Thank you! Professors always manage to make the material out to be much more difficult than it actually is. This was extremely helpful
Yes I understand that frustration, it makes me wonder sometimes if they truly understand topic.
@@randerson112358 SO TRUE! Seems like they are just making it extra difficult and abstract sometimes
Finally! I spent days trying to find something to explain this because i could not connect the info in my book. It simply showed the same function that you started with and then the conclusion. asked some math majors and EE engineers I work with, couldn't figure out how the book went from start to finish either. So thank you very much
Finally makes sense ! currently studying this for my algorithms final, you are a life saver man
+BlazedOutTurtle , thanks glad this video helped !
just switching the big o formula around so it becomes a ratio simplifies this so much. my exam in the morning thanks you
Read the book, couldnt get it. Watched your video, everything became clear. Thanks a lot for great explanation.
Thank you for watching, the text books can be a bit hard to understand at times.
Great video.
i can't believe you explained this concept this simply. Thanks to infinity.
Glad you liked it man !
This is fantastic. Was just staring blankly at my prof's explanation and it didn't really help me. This is the first video I found that actually made it easy to understand. This will really help me in my mid term upcoming in the next two weeks.
Glad it helped!
This is the best explanation I've found so far on this topic
Thanks !
I've been struggling to understand what values to make n and the constant. Nice to see a clear demonstration on why you arrived at n = 4 for the proof unlike many other resources I've looked at.
the best, simplest, and clearest explanation ever. thank u
I'd been struggling to understand this topic, and none of it made sense until I came across your video. Thanks so much for the explanation! :)
Hey ! Thanks I am glad this video could help.
At about 1:48 you say: We want to find a function bigger than this one. Why is that? Why do you replace everything that's not n^2 with n^2? What's the logic behind it? I've seen it in other problems being solved and I still don't get it. Thanks!
The reason for the bigger function is to derive a constant called C that will satisfy the equation which is f(n) / g(n)
R. Anderson, thank you for the step-by-step explanation! I will definitely be checking out more of you videos.
How did you transform (n^2 + 2n + 1) / n^2 (n^2 + 2n + 1) / n^2?
Raphael S Carvalho , good question, in this video I took a short cut for time and showed that (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2 for all n > 1 which is true.
There was NO transforming of the original equation from (n^2 + 2n + 1) / n^2 (n^2 + 2n + 1) / n^2, it was a statement or a fact that (n^2 + 2n^2 + n^2) / n^2 is ALWAYS greater than (n^2 + 2n + 1) / n^2 whenever the value 'n' is greater than 1. You can see the value on the left hand side grows faster when you add larger and larger values for n.
For EXAMPLE:
let n = 10
Then the inequality equals the following by substitution:
ORIGINAL inequality: (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2
After Substitution: (10^2 + 2(10^2) + 10^2) / 10^2 > (10^2 + 2(10) + 1) / 10^2
Now to simplify:
(100 + 200 + 100) /100 > (100 + 20 + 1)/100
= (400)/100 > (120)/100
= 4 > 1.2 which is TRUE
Now let's use a bigger number like 50:
Let n = 50
Then the inequality equals the following by substitution:
ORIGINAL inequality: (n^2 + 2n^2 + n^2) / n^2 > (n^2 + 2n + 1) / n^2
After Substitution: (50^2 + 2(50^2) + 50^2) / 50^2 > (50^2 + 2(50) + 1) / 50^2
Now to simplify:
(2500 + 5000 + 2500)/ 2500 > (2500 + 100 + 1) / 2500
= (10000)/2500 > (2601)/2500
= 4 > 1.0404 which is TRUE
Notice that the value on the left always equals 4 as the value 'n' increases, and the value on the right gets smaller as the value n increases, this shows the function on the right hand side will always be less than the number 4 as long as the value n is greater than 1.
NOW for your question, which I believe you meant is, how do I know that the second function (n^2 + 2n^2 + n^2) / n^2 is ALWAYS greater than (n^2 + 2n + 1) / n^2, and the simple answer is by doing an algebra proof or using intuition. The intuition and proof are below:
Intuition:
If I have a number (a constant) divided by a variable, the over all value of that number will always decrease, because n grows faster than a constant. A constant doesn't grow at all.
For Example
1/n will always be less than or equal to 1(a constant) whenever n is greater than or equal to 1.
function: 1/n
let n = 1, function = 1/1 = 1
let n = 2, function = 1/2 = .5
let n = 3, function = 1/3 = .333...
let n = 4, function = 1/4 = .25
so the constant value that 1/n will never be greater than is 1, whenever n is greater than or equal to 1.
Hence: 1/n = 1
second example:
Here I will use a denominator that grows faster then it's numerator like the above example:
function: (n+1) / n^2
let n = 1, function = (1 + 1) / 1^2 = (2)/1 = 2
let n = 2, function = (2 + 1)/ 2^2 = 3/4 = .75
let n = 3, function = (3 + 1)/ 3^2 = 4/9 = .44444.....
so the constant value that 1/n will never be greater than is 2, whenever n is greater than or equal to 1.
Hence: (n+1)/ n^2 =1
So this means for my orignal function '(n^2 + 2n + 1) / n^2', as long as the denominator is the biggest possible value or grows the fastest there is a constant that the function will be less than, in the above cases, that constant is a 1 for example 1 and 2 for example 2.
OKAY HERE IS YOUR ANSWER:
By making every number in the numerator divisible by the denominator (AKA the highest possible value) we get a constant that the original function is less than.
From example 1, the function 1/n will never be greater than 1
By using the above principle (making the numerator a multiple of the denominator) we can see this is true.
Ex1:
Original = 1/n
Transformation = n*(1) / n = n/n = 1 (The constant that the function will never be greater than)
Hence:
n/n > 1/n whenever n > 1
Ex2:
Original = (n+1)/n^2 (Notice both n and 1 grow slower than n^2)
Transformation= (n^2 + n^2)/ n^2 = 2(n^2)/n^2 = 2 (The constant that the function will never be greater than)
Hence:
(n^2 + n^2) / n^2 > (n+1)/n^2 whenever n > 1
and so it follows to find a constant that our original function will always be less than we need to do a similar 'transformation'
Ex3:Original = (n^2 + 2n + 1) / n^2
Transformation = (n^2 + 2n^2 + n^2) / n^2 = 1 + 2 + 1 = 4
So 4 is the constant that (n^2 + 2n + 1) / n^2 will always be less than whenever n > 1.
Few, last proof this is always true
Using the inequality:(n^2 + 2n^2 + n^2) / n^2 >= (n^2 + 2n + 1) / n^2 , and n >=1
1) Multiply both sides by n^2 to get the below:
(n^2 + 2n^2 + n^2) >= (n^2 + 2n + 1) whenever n >= 1
2) Subtract n^2 from both sides to get the below:
( 2n^2 + n^2) >= (2n + 1) whenever n >= 1
3) Subtract 1 from both sides to get the below:
(2n^2 + n^2 - 1) >= (2n) whenever n >= 1
4) Subtract 2n from both sides to get the below:
(2n^2 + n^2 - 1 - 2n) >= 0 whenever n >=1
5) Add like terms and rearrange to get the below:
(3n^2 - 2n - 1) >= 0 whenever n >= 1
6) Divide both sides by n^2
(3 - 2/n^2 - 1/n^2) > 0 , whenever n >= 1
Note: 2/n^2 is always less than or equal to 2 and 1/n^2 is always less than or equal to 1 whenever n increases since the smallest value n can be is 1
7) Rewrite the equation as the maximum values 2/n^2 and 1/n^2 can be
(3 - 2 - 1) >= 0 ==> (1-1) >= 0 ==> 0 >= 0 which is always true.
I hope this spreads some light on the reason why I said
(n^2 + 2n^2 + n^2) / n^2 >= (n^2 + 2n + 1) / n^2 , and n >=1
randerson112358
is there any short explaination
Your in depth explanation of this rocks!! Thanks for taking the time. It was exactly what I wanted to know.
@@dynamohack Consider a simplier example where we know that n²/n² is always ≥ to n/n² for all n ≥ 1.We can use this fact to find an upper bound that suggest that n²/n² = 1 thus 1 is always ≥ to 1/n² for all n ≥ 1.
In a similar fashion (n²+2n²+n²)/n² will always be ≥ to (n²+2n+1)/n² for all n ≥ 1. By breaking (n²+2n²+n²)/n² into independent fractions we get n²/n² + 2n²/n² + n²/n² simplifies to 1+2+1=4 thus 4 is always ≥ to (n²+2n+1)/n² for all n ≥ 1.
@@luisojedaguzman7624 i cleared my exam 2 years ago thank you
please do more proofs and explanations especially the complex ones
Thanks for the comment, I may do more complex proofs in the future.
At 2:33 you say for all n greater than 1, but then you pick 1 as your input and then say 4 is greater than the right side. Don't you have to pick a number greater than 1 for that to make sense? Try plugging in 1 to both sides of that inequality, you'll see that you get, 4 > 4, which is not true.
You're awesome for this! You made it so simple! Thank you so much for making this 9 years ago lmao! Wish me luck for my test today!
Good luck!
Thank you. I'm struggling in online school and this is a big help
Glad the videos help!
Omfg thank you! Idk why RUclips doesn’t recommend you. Literally just saved my ass since my professor doesn’t teach shit
Thanks, hopefully RUclips will eventually start recommending some of my videos that are helpful for others.
@@randerson112358 I really like your videos, also would you be interested if in tutoring via zoom if I paid you. The class is Algorithm techniques
OOh My god! This just made things clear! Been re-reading my textbook trying to understand this concept all week. But this video helped me finally understand big-o proof in a matter of minutes.
Wish I found this sooner. Thanks!
Thank you so much. I've been struggling with Big O notation and pulling my hair out trying to figure it out. Nothing has helped clear the fog. The text book just didn't make sense nor did any of the other material I've read online. This is the first video that actually made sense to me.
+saberdino966 No problem , I definitely understand your frustration. I could barely understand the material in my classes, and had to go and ask other professors, and students to give me some clarity on this subject.
Keep learning this stuff and any computer science topic, it only gets better and more interesting. I really enjoy this field.
randerson112358
Thank you! I couldn't understand until I saw your video
great explanation
Dude this is awesome! You spell it out very well. Thanks, this was a breakthrough for me.
holy shit ,it was a great pity that i find your video so late .i had just failed my exam ,but after your tutorial I think i can get it.
Thanks man helped clear things up right before my test!
thank you, this is the only explanation that I found that actually helped.
Thanks Man this relay helped me! I wish you the best of Life!
+Brian Cain thank you!
This was a godsend man, thanks so much!
A true voice of reason out of nowhere.
Thanks!
Awesome video. This really helped clear some things up for me. I see that you have some other videos up, which is great. If I could make one request, please put your camera on a tripod or some stable surface. I'm sure that I'm a fringe case, but the slight wobble of the video is enough to make me motion sick.
thanks, I plan on getting something to make my camera stable
so much better than my teacher
at 2:30, why do you make it n > 1 instead of n >= 1?
You are a life saver.
Thank you so much.
But how did you know to choose k = 1? Why wasn't it k = 8, or k = 6? Or some other number? What made you choose that? Please explain your thought process.
Hi Veritas,
I could've chosen k= 8 or k=6 or k= 89 or k = 100000 , as long as k is some number greater than 0.
Notice that in this video if k=8 then it still satisfies the big oh definition, since I chose values of n >= 1 this implies values of n>=2 and n >= 3 and so on.
So I think you may be a little confused as to what k is and why do we need it in the definition to prove big-oh.
The definition of Big-Oh: A function f(n) is said to be O( g(n) ) if there exist two positive constants C and k that will make the following equation true;
f(n) k
The value of k replaces the input value n, in the function.
For example
Let f(n) = n^2 and let g(n) = n^3
Let's create a chart for the vaues of n
n | f(n) | g(n)
-------------------------
0 | 0 | 0
Bro I was just about to give up hope then I foiund this!! Thank you
Thanks! I can't find this explanation anywhere
wow, you make it super cool, keep it up bro.
+Samuel Hailai thanks
Appreciate it, this helped a lot. I actually had to prove an almost identical problem.
+Dale Pollitt that's great hear!
Since ...
At 3:54, how does proving:
(n^2 + 2n + 1) / (n^2) = 1
Mean that f(n) = O( g(n) )?
+Kenny Worden
All we had show is f(n) = k this proves f(n) is O( g(n) )
Rewrite the equation/ definition to get the below:
f(n) / g(n) =k to prove f(n) is O( g(n) )
In this example :
f(n) = (n^2 + 2n + 1)
g(n) = (n^2)
C = 4
k = 1
Notice as the value of n increases noted by n>=1, the value of f(n) /g(n) decreases.
Specifically if you plug in any value for n that is greater than 1, then
(n^2 + 2n + 1) / (n^2) will always be less than or equal to 4.
NOTE: if you don't see this then plug in values for 'n' and you will notice that (n^2 + 2n + 1) / (n^2) will get smaller and smaller as n gets bigger.
For example plug in n=1, then n=2, then n=3 and so on until you see the decreasing pattern.
So since we proved the statement f(n) / g(n) =k is true, we proved f(n) is O( g(n) ).
or more specifically
Since we proved (n^2 + 2n + 1) / (n^2) = 1 is always TRUE ,
We proved (n^2 +2n + 1) is O( (n^2)
randerson112358
Can you simplify the equation and do the same calculation and proof?
do you also have a video to proof f e O(g) is equivalent to g e O(f)?
you can solve it much easier considering the limit when n goes to infinite, right? I am still learning but I think the limit must be a constant for it to be big O
This is so helpfull, Thank you!
Thanks for watching!
thank you too randerson112358
At 2:30 why did you decide on n>1, not n>=1? Thanks for the very helpful video
I chose n > 1, because it makes the overall statement true.
Hey, look, another R. Anderson! Thanks for the vid, it's definitely helpful to see this kind of thing worked out step by step.
Thanks
You the real MVP.
Haha thanks !
Thank you a lot man really helpful video
This is the best explanation of big-oh I have seen so far. Thank you very much for saving a student from committing suicide( just kidding). You are great
Lol yeah proving big oh was tough for me to understand as a undergraduate .
My text book is garbage this semester, wish I would of found this video sooner.
4:00 No! Why did you remove that? I wasn't done writing it down...
+Mira Bellenbaum lol pause the video about 3 seconds before then 4:00
8 years ago randerso112358 woke up and decided to save my homework from today
What if instead of the constant at the end being 1, it's a bigger number? Say 100, then instead of n^2 would it just be 100n^2
Thank you. This explanation helped me a lot. :)
Great explanation! Thank you
Thank you very much !
what do you do when you are given a logarithmic function?
great thanks , I have a question what is(k) as c or they are different
This video is awesome, thank you so much!
Thanks for watching !
Thank you so much for this video!
In this case wouldn't f(n) be big-theta of g(n)? If C was 1 then f(n) > g(n) for all n > 1.
Great explanation!
Thank you Cindy !
How would i do if my g(n) is 3n^4+6n^2+8n+2 and f(n) is 8n^3+4n^2+5n+1. Would you please guide me through it.
Thanks so much, helped a lot.
Great to hear!
If you put n=1 in n^2+2n+1 /n^2 , it is also equals to 4. So how is 4 > 4 ? It's only if n>1 , but when n>1 then it's no longer 4. I don't get it.
Hi, I am not sure during which time on the video you are referring. However we must show f(n) k
So this means that we our constant can be equal to or greater than 4 whenever n>1
This is bad ass!! Thanks a million. Whoever gave the two thumbs down. Whack!!!
Dude you're a lifesaver and a saint!!
Thanks!
Why the hell does my textbook use this complicated algebra when this method is so much easier?
School sucks man i hate this. Thank u
gotta love paying thousands of dollars to go to hours of lectures only to have to watch 3 minutes of a youtube video of a dudes whiteboard in 2014 to learn this
Extremely helpful. Thank you so much!
Thanks, this was a topic I used to struggle with as well. I am glad that I can help someone else !
Thanks! It's so helpful for me ~~
how did you get the number 4???
at 3:00 to 3:09, I think you are making a mistake here...
If we are looking F(n) > f(n), then n can NOT equal 1 in this case, it doesn't make sense.
for example... n = 1 (which is what you did at 3:00
(1^2 + 2(1^2) + 1^2)/1^2 > (1^2 + 2(1) + 1)/1^2
(1 + 2 + 1)/1 > (1 + 2 + 1)/1 = 4 > 4... Which is not correct for n = 1.
In fact... I believe that n needs to stay n >= 1... Unless I'm missing something very fundamental here. It makes no sense to have n = 1.
I think logically, what you did was correct, but stating that n should be n > 1, and then using n = 1 to prove that f(n)/g(n) >= C for all n >= 1 is a bit misleading.
Hi Felxaga ,
I do believe you are missing something fundamental.
From your comment:
"(1^2 + 2(1^2) + 1^2)/1^2 > (1^2 + 2(1) + 1)/1^2
(1 + 2 + 1)/1 > (1 + 2 + 1)/1 = 4 > 4... Which is not correct for n = 1."
You are missing the '=' sign, it is supposed to be 4 >= 4, which is true, but I did not substitute 1 for n.
I do not know where you are seeing n = 1, n is greater than or equal to 1.
If you are confused on how I got the number 4, I used division.....
[ (n^2) + 2(n^2) + (n^2) ] divided by (n^2) = 1 + 2 + 1 = 4.
Lets simplify:
[ (n^2) + 2(n^2) + (n^2) ] /(n^2)
= (n^2)/ (n^2) + 2(n^2)/(n^2) + (n^2)/(n^2)
= 1 + 2(1) + 1
= 4
I divided by n^2 to get 1, I used algebra, no substitution where n=1
This is LOGICALLY correct, plug in any number for n that is greater than 1 into the following equation and see if it's true:
Equation: f(n) / g(n)
Yeah... yeah.... this is what not doing any math for several years does to you... you start missing the very fundamentals... HOW DID I MISS THIS!?!?!?
Would you believe I used to tutor in advanced calculus just 3 years ago?
Anyways, thanks for pointing that out for me, I need to whip my brain back into shape >.
It happens to the best of us, we are only human :)
Glad I could help.
Thanks.. It was helpful a lot 👍🏼
Why did you choose 1 for k?
Thanks, great help
Thank you for the video. Do you always use the value 1 for constant?
+Made Different thank you and not always.
Sorry I might have phrased my question wrongly. What I meant was do we always use n >= 1?
I have seen many examples online and all uses the value 1 but I do not understand why 1.
+Made Different the answer is no. You can use any other constant you want.
Okay noted. Thank you for your reply. Cheers!
Thanks for this!
Jovaughn Lockridge Thank you for watching
very helpful thanks!!
Thank you so much bro!!!
Great work! Youre awesome :D
why is g(n) being rewritten to n^2?
is value of c and k unique
You're wonderful!!!
THANK YOU SO MUCH!
Thanks for watching!
What about logs, trig, fraction. ...
I used your method but it gave me a negative constant C. I wish you would do more challenging questions.
THANK YOU
Thanks for watching!
thank you man...
Funky Attitude thanks
pls can u explain the second step
din't get it
How do you know that g(n) is n^2?
Thanks for share, man.
Thanks!
isn't it wrong, f(n)=big oh g(n), is not that the values that equals to one another, but there exists g(n)
Wow Differential Equations, that's very good !
You are correct, but so many teachers use the '=' operator and many older papers do as well, that I decided to continue using that notation as well to help others. I try to mix it up in all of my videos.
But Big O is a set of functions which is why we use there exists or belongs to instead of equal. I don't know why '=' was ever used, but I do know mathematicians/teachers still use that notation today.
thank you sooo much!