Prove Big-O
Вставка
- Опубліковано 17 вер 2014
- Learn how to prove computer science asymptotic analysis.
This video proves f(n) = O( g(n) ) or in this case f(n) = O(n^2).
Big Oh proof by definition.
Easy Algorithm Analysis Tutorial:
www.udemy.com/algorithm-analy...
Recurrence Relation Tutorial:
www.udemy.com/recurrence-rela...
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...
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!
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
R. Anderson, thank you for the step-by-step explanation! I will definitely be checking out more of you videos.
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 !
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!
Finally makes sense ! currently studying this for my algorithms final, you are a life saver man
+BlazedOutTurtle , thanks glad this video helped !
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.
just switching the big o formula around so it becomes a ratio simplifies this so much. my exam in the morning thanks you
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
Dude this is awesome! You spell it out very well. Thanks, this was a breakthrough for me.
Someone give this guy tenure already!!!
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!
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.
i can't believe you explained this concept this simply. Thanks to infinity.
Glad you liked it man !
Thanks man helped clear things up right before my test!
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.
thank you, this is the only explanation that I found that actually helped.
This is the best explanation I've found so far on this topic
Thanks !
the best, simplest, and clearest explanation ever. thank u
Thanks Man this relay helped me! I wish you the best of Life!
+Brian Cain thank you!
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.
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
Thank you so much for this video!
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.
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
You are a life saver.
Thank you so much.
Thank you. This explanation helped me a lot. :)
Thanks.. It was helpful a lot 👍🏼
Thanks! I can't find this explanation anywhere
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
Thank you! I couldn't understand until I saw your video
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!
Great work! Youre awesome :D
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
Thanks! It's so helpful for me ~~
Omfg thank you! Idk why UA-cam doesn’t recommend you. Literally just saved my ass since my professor doesn’t teach shit
Thanks, hopefully UA-cam 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
Thank you so much! So helpful!
Thank you a lot man really helpful video
This was a godsend man, thanks so much!
Can you simplify the equation and do the same calculation and proof?
Since ...
this is wonderful, thank you
Thank you. I'm struggling in online school and this is a big help
Glad the videos help!
Thanks for this!
Jovaughn Lockridge Thank you for watching
great explanation
Bro I was just about to give up hope then I foiund this!! Thank you
great thanks , I have a question what is(k) as c or they are different
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
Great explanation! Thank you
Thank you very much !
very helpful thanks!!
You're wonderful!!!
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
Thanks! You rock!
thank you too randerson112358
A true voice of reason out of nowhere.
Thanks!
Thanks, great help
8 years ago randerso112358 woke up and decided to save my homework from today
This video is awesome, thank you so much!
Thanks for watching !
Thank you so much bro!!!
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 !
Appreciate it, this helped a lot. I actually had to prove an almost identical problem.
+Dale Pollitt that's great hear!
so much better than my teacher
Thank you so much to help out
do you also have a video to proof f e O(g) is equivalent to g e O(f)?
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.
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
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 .
wow, you make it super cool, keep it up bro.
+Samuel Hailai thanks
This is bad ass!! Thanks a million. Whoever gave the two thumbs down. Whack!!!
what do you do when you are given a logarithmic function?
Thanks for share, man.
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:30, why do you make it n > 1 instead of n >= 1?
Great explanation!
Thank you Cindy !
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
This is so helpfull, Thank you!
Thanks for watching!
Thanks!
OMG THANK YOU
Thank you!!!!
Thanks so much, helped a lot.
Great to hear!
My text book is garbage this semester, wish I would of found this video sooner.
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)
thank you!
thank you.
pls can u explain the second step
din't get it
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.
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.
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
how did you get the number 4???
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
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
THANK YOU SO MUCH!
Thanks for watching!
You the real MVP.
Haha thanks !
I'll watch the playlist of Algortithm analysis of this chanel because I am taking Algorithms II when i didn't went to Algorithms I xd
Why did you choose 1 for k?
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!
Thank you!
Thank you for watching Natsnet !
What about logs, trig, fraction. ...