How to Prove or Disprove Big-O - Introduction to Computer Science
In this video, I will show you how to prove or disprove Big O. I will also go over the formal definition of the formula Big O using asymptotic notation to determine the runtime of an algorithm. For example, you are asked to prove that a function 2n+3 is O(n). By the definition of big O, f(n) is O(g(n)) if you can find a positive constant c and a positive integer nₒ such that f(n) is less than or equal to c times g(n), for all n is greater than nₒ.
Knowing how to prove that something is Big O or not Big O is an important skill that Computer Science CS and Math students need to know about time complexity and growth of functions. It is likely that you will encounter this topic in your typical Data Structures, Discrete Mathematics, or Analysis of Algorithm courses at University.
I will also how you how to prive Big Omega Ω or Big Theta θ. If you enjoyed this video, please don't forget to comment down below and also subscribe if you haven't already!
Пікірлер: 48
youre the best tutor in the game for computer science & math, please don't stop making these videos
@QuocDatPhung
8 ай бұрын
Thanks very much! I will never stop making videos :)
Thank you so much! This is what I was looking for.
finally well understand. Thank you very much
@QuocDatPhung
3 күн бұрын
Thank you for your kind words Shuyao! Please kindly share with your friends and subscribe ~ all of my CS videos are in this link: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
So much helper than a lecture in colleage,much straightforward,i will recommend to my classmate,thanks!!!
@QuocDatPhung
5 ай бұрын
Thanks so much! Please also kindly subscribe! You can find all of my Data Structures and Algorithm lessons in this playlist: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
@nandor2329
3 ай бұрын
Abssolutely agree, what a man, Thanks !!!
Excellent video! 🎉
1.50 mins and I'm finally understand the concept. Thank you so much!
@QuocDatPhung
3 ай бұрын
I'm glad it was helpful! You can find the Big Ω video here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
This was really helpful, thank you
@QuocDatPhung
13 күн бұрын
You're welcome Joseph! Please kindly share and subscribe~ you can find all of my CS videos in this link: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
Than you so much you made it so easy to understand how to do the formal way.
@QuocDatPhung
4 ай бұрын
Thanks so much M3ga! I will try to work on Big Omega and Big Theta once I finish my exams haha. Please don't forget to subscribe! As well, you can find all of my Data Structures & Algorithms videos in this playlist: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
that's what im looking for man!
@QuocDatPhung
4 ай бұрын
I'm glad it helped! You can find all of my Computer Science videos here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
Thank you very much for making me understand this thing!!!😭
@QuocDatPhung
4 ай бұрын
You're very welcome! You can find all of my CS videos in this playlsit: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
What a great channel !!😮💓💓
@QuocDatPhung
4 ай бұрын
Thanks so much! You can find all of my CS videos here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
Bro, I have an exam in couple of days and you saved me, may god bless you
@QuocDatPhung
3 ай бұрын
Thank you! Don't forget to see my video on Big Omega! You can find the link here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
Thank you!
@QuocDatPhung
4 ай бұрын
You're welcome! You can find all of my CS videos in this playlist (don't forget to share and kindly subscribe!): kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
bro is the GOAT
@QuocDatPhung
3 ай бұрын
Thanks so much Thiên Phúc! I'm working on the one for Theta and Omega; you can find all of my CS videos in this playlist here (don't forget to share and kindly subscribe!): kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
thank yooooou
@QuocDatPhung
14 күн бұрын
You're welcome Muhammed! Please kindly share and subscribe~ you can find all of my CS videos in this link: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
super video
@QuocDatPhung
4 ай бұрын
Thanks so much! You can find all of my CS videos in this link here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
Hi thank you for your video. To prove big Theta, do I have to prove big O and big Omega and if both are true big Theta is proved? Also could you tell me following: The way to find a constant c, we are choosing the one that we are trying to proove (for example xxx = O(n²). So on the right side of "is larger or equal than) all of the values will have to be larger than on the left side but max. as n². What happens if we cannot choose a larger one by this definition? So if it is 100n³ = O(n²) we cannot choose n² as the largest. Many thanks from Germany!!
@QuocDatPhung
2 ай бұрын
I actually have videos on Big Omega/Theta! You can find it here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
cảm ơn bạn ơi
@QuocDatPhung
4 ай бұрын
Không có gì bạn! Bạn có thể tìm tất cả clip của mình về Computer Science trong link này nhé (bạn đừng quên chia sẻ và đăng kí hihi): kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
Hi could I ask what n not is? In our class we use C and K but I find your method to be easier.
@QuocDatPhung
2 ай бұрын
N not is the same as k :) some textbooks use different variables but they mean the same thing! Also I'm really glad to hear that you find my method easier! I would really appreciate if you could kindly share or subscribe ~ you can find all of my CS videos in this link: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
For the 5n^2 + 3nlogn + 2n + 5 is O(n^2) I got constant C = 12 because instead of raising nlogn to n^2 I just dropped it all together 5n^2 + 3nlogn + 2n + 5
@QuocDatPhung
4 ай бұрын
Yes that should be fine :) You can find all of my CS videos here: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
I love you
@QuocDatPhung
Ай бұрын
Thank you! I have videos on Big Theta and other topics too! Pls don't forget to share with your classmates and kindly subscribe ~ you can find all of my CS videos in this link: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC
Don't you think c^n is bigger than n^c
@QuocDatPhung
Ай бұрын
Yes, in the video I said that c^n is bigger than n^c at 5:20
howd you get 2n + 3n
@QuocDatPhung
4 ай бұрын
Hi Timmy, please let me know the timestamp of the question you're referring to.
@QuocDatPhung
4 ай бұрын
Do you mean the one at 1:12? Ok, now imagine you're in a math class. Let's say you have f(x) = x and g(x) = x^2. Since g(x) is quadratic, and f(x) is linear, then it must be that g(x) > f(x) meaning g(x) will at some point intersect f(x) and be above it forever. Agreed? You can also pick g(x) = x^3 or whatever you want and g(x) is still greater than f(x). Now, coming back to 1:12, let's say f(x) = 2n + 3. Can we find a function greater than this one? Yes. We can say the function 2n + 3n or 2n^2 + 3 or whatever you want. But for the sake of simplicity, let's pick 2n + 3n. Therefore, you get 2n + 3 < 2n + 3n. Does that make sense? Don't overcomplicate it. It's easier than it looks.
@seketorianGaming
4 ай бұрын
@@QuocDatPhung Thank you, this helped. And you're correct I think I over complicated it.
@QuocDatPhung
4 ай бұрын
@@seketorianGaming No worries! You can find all of my Data Structures & Algorithms videos in this playlist: kzread.info/head/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC