How to Prove or Disprove Big Ω - Introduction to Computer Science

In this video, I will show you how to prove or disprove Big Ω (Big Omega). I will also go over the formal definition of the formula Big Ω using asymptotic notation to determine the runtime of an algorithm. For example, you are asked to prove that a function 2n+3 is Ω(n). By the definition of big Ω, f(n) is Ω(g(n)), or f(n) is Big Omega of g(n) if you can find a positive constant c and a positive integer nₒ such that f(n) is greater 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!

[@OggyShows]

you look very smart

[@QuocDatPhung]

Haha thank you! Please share with your classmates to help them in this course and also kindly subscribe ~ you can find all of my Computer Science videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@akashsangwan3964]

You know how to teach!!

[@QuocDatPhung]

Thank you Akashsangwan! Don't forget to share with your classmates and kindly subscribe ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@guestboy342]

I have a question. Instead of the trial-and-error method in the video, is it possible to solve for nₒ or n using the inequality?
Thanks in advance! Your channel is underrated and I hope it grows bigger in the future.

[@QuocDatPhung]

Yes you can use the inequality to solve for nₒ. However, let's say that inequality is very complicated like nlogn + sqrt(n) >= c * nₒ or something like that. It's very hard to solve for nₒ so that's why I recommend trying nₒ = 1, 2, 3, ... until it works. You can find all of my CS videos in the following link (don't forget to share and kindly subscribe!): th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@kisuany]

you're incredible thank you so much for your videos! they are a great help :)

[@QuocDatPhung]

You're welcome Kisuany!! I'm really glad you enjoyed my video! I would really appreciate if you could share with your classmates or kindly subscribe ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@MohdAasif-bg4wl]

11:28
nlogn is greater than n in time
so, for omega the value should not be less than n but u wrote nlogn which is greater ?
i know in Big O we can take the values greater than the current time function can we do same for theta?

[@QuocDatPhung]

Ok, let's go back to 10:53 to see why
I used the example 3x - 2 = 3x -2
From there we know 3x - 2 >= 3x - 2x.
That's because we are subtracting 2x on the right hand side (subtracting more than the left hand side).
Make sure you understand this. Very important.
Now, let's look at 3nlogn - 2n = 3nlogn - 2n.
From there we know 3nlogn - 2n >=- 3nlogn - 2nlogn.
Since nlogn is greater than n, we are now subtracting more on the right hand side, which is why the inequality sign is >=
Does this make sense? Let me know.
All of these problems and solutions are from the Data Structures and Algorithms in Java textbook (6th edition) by Michael Goodrich.