1.9 Properties of Asymptotic Notations
Vložit
- čas přidán 8. 09. 2024
- Properties of Asymptotic Notation
General Property
Reflexive Property
Symmetric Property
Transpose Property
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
Abdul Sir, i've been in IT field for 25 years now and learning DSA just out of interest. I think you explain very complex things in the simplest possible manner. That is a god's gift. Thank you for the wonderful content😊
I can't believe my university teacher has copied each and every notes of yours even the examples are also same and he has done Phd from IIT indore, I think in future there will be no need to pay high fees for studies because we can get the same skills without doing graduation and matric degree.
which university?
Can you help me how these notations help in coding ?
your teacher might be reading your comment now
@@HG-xx1ts exactly !! Good luck to his grades 🙂
@@daisywhite5154 but the teacher can't find his name here😉
you sir, are an absolute legend! thank you for helping thousands of desperate students with bad profs getting through CS studies
Sir you are life saver.humare AD kya padhate kuch samjh nhi aati. Kal mera 3rd sem hai aur aaj mein idhar se sara samjh payi. Country needs more man like you sir. Thank you so much.
Exam in 3 hours, this man is a life saver.
exam in 10 hrs xd
Exam in 39 hours ;C
exam in 144 hours, this man is a life saver.
Exam in within 1 month
exam cancelled due to COVID :D
Sir You are the most straightforward teacher I have ever seen thank you for helping me
Happy Guru Pornima guruji 🙏
Thank you so much sirji for being such a wonderful teacher for all of us😊
We are blessed to have you 🙏😊
Sir your content is so valuable that every student and professional will find it useful. You will never get a single negative comment. Thank you so much 🙏
Excellent progression and crystal clear content. Thanks!
Can you help me how these notations help in coding ?
@@ankitkhasgiwale1229 DAA concept won't be helping you directly for coding, better go and learn the libraries and loops for programming, this all is the concept under the table...programming is practical working
Happy teacher's day sir, an absolute legend of CS
Thanks Dear.
God Bless You.
@@abdul_bari OMG, thank you sir for replying
Good well Accurate Knowledge Providing Lecture Great Work Sir And Thank you For Being Here Teaching And Clearing All Our Doubts
Can you help me how these notations help in coding ?
@@ankitkhasgiwale1229 bro you won't be writing these notation when you code...these are like the theorems in math subject. They tell you how time complexity works, and how to compare which algorithm is better. They are theory.
Thanks sir for such simple language explanation .
It help lot for those who are not from cs to understand concepts.
Assalamu Alaikum sir
excellent & crystal clear concept
love from Bangladesh 🇧🇩
thnx sir for your kind effort; your lectures are helping a
lot in enhancing our competitive coding skills
Even me
انت راجل مية مية you are great man ,god bless you
An absolutely brilliant teacher you are Sir, thank you very much and I have also learned C++ from your course on Udemy, Love you Sir, God bless you.
Can you help me how these notations help in coding ?
Hello, please share the the link of that c++ course from Udemy here.
Great videos sir, This helps a lot. Could you please make video for Insertion sort as well.
no
Sir u r best teacher I have ever seen. Can u pls upload java course in udmey
He has uploaded it on Udemy
Type Abdul bari Java on Udemy
What a perfectly you have gone through!! 👌👌
Thanq sir i got all my doubts clear by watching this video
Thank you very much. You are a genius. 👍👍🔝🔝👌👌🙏🙏
You are Great sir. Thank you very much for your lectures.
Thanks
Sir, how come you make things so simple that anybody can plainly understand! Hats off to you!
you are amazing sirrrr!!
You're Awesome Sir God Bless You...
this helped me alot
thank you very much really outstanding.
I appreciate and a big thumbs up , but can u relate these functions(f(n) and g(n)) to Algorithms practically so that the audience can benefit from it, which i mean to say write a simple program and relate 1) f(n) 2) g(n) 3) the constant to the program .If you can that would be a great help
watch playlist
Again one more impressive video really you nailed it sir. Thanks for teaching us sir.
Jai hind sir. You are the great.
Thank you so much, sir, for the detailed explanation
This is very helpful video thank you
nice lectures.
kind of helping alot
The best explanation on this topic...
the biggest asset to the dsa community
thank you for the great lectures sir..please add amortized analysis .
best explanatory in world
Thanks sir for your content.
U really explain all the topics efficiently but I have a doubt which is sir , u use big theta notation in symmetric properties but we can use other notations as well and one more thing sir u use n^2 in that example which is wrong for theta notation.
thank you so so much sir for helping us out
Thank you sir!!
I really loved your vedio please make more such vedios
I request you to make vedios on different topics too
Thank you, you were so helpful
Thanks sir !
THANK YOU SIR FOR THE HELP.
Hi Sir,
In Reflective property, if function is a n! then Big-Oh will be O(n^n). How this satisfies the property??
I think Reflexive property will not work here
Big-Oh is anything between O(n!) and O(n^n), so it satisfies.
Is Reflexive property is applied to Omega and Theta or it's only valid for Big-oh? Thank you very much.
its for all
Can we use reflexive property for n! Also that is if we want to find the time complexity of n! It can be O(n!) Or omega(n!) Or theta(n!) ???
You are a SAVIOR
best explanation
so I can prove theses properties by writing examples like you did Or there is another way? : )
Sir for the properties of asymptotic notations
when f(n)=O(g(n))
d(n)=O(e(n))
then for f(n)*d(n)=O(g(n)*e(n))
but sir when both are equal, will the answer be g(n) or e(n)?
answer will still multiplication as left side is multiplying so their time class will also multiply to get the highest order as we get in previous by applying max function
good lecture....
Aslamoalikam Sir! I am bit confused please explain .
In previous lecture you are saying that f(n)=n! ... 1
It says that will IF O big and Omega is the same, THEN theta is also the same, in your example, Obig and omega isn't the same!
Sir could you please suggest a good book to study this subject
Sir why we will neglect the cofficient of function
like 2n+3 then Big-oh(n) & also for 6n+9
Because we are finding approximate time(time complexity prior which is approx value) hence the for large value of n like 10^6 it doesn't matter whats the coefficient is and what is added or substracted to it. We only focus on the largest power of n present in the equation.
@@utkarshsingh3275 you say that n has larger value it mean coefficient not matter but i didn't understood if 2n is write then it value become double of them mean according to your ex. 2*10^6 it is huge difference
@@ayushmaheshwari5805 if u are comparing with other values it makes difference but if you are talking about n*10^6 taken individually then co efficients and constant doesn't play any role. We ignore them. That's why all the time complexities are free from constants, whether it be multiplied or added.
Like if u are comparing 2n and 3n then ofcourse the coefficient matters. But of you take them separetly then both will have T(n) = O(n)
Awesome work
Thank you, sir
Thanks
Thank you 🙂.
Sir in the first example, can (nsquare) be big O of (2nsquare +5)
thnk youuuuuuu so much
Why transpose symmetry is not applicable for big theta small o and small omega?plzz help
why we have to learn all things ? where we use this concept?
THANK YOU SIR
Me watching this vdo just 3hrs before exam
Summary:
1) General properties (0:00)
* If f(n) is O(g(n))
- Then a * f(n) is O(g(n))
* If f(n) is Omega(g(n))
- Then a * f(n) is Omega(g(n))
* If f(n) is Theta(g(n))
- Then a * f(n) is Theta(g(n))
2) Reflexive properties (2:10)
* If f(n) is given
- Then f(n) is O(f(n)) and also f(n) is Omega(f(n))
3) Transitive (3:33)
* If f(n) is O(g(n)) and g(n) is O(h(n))
- Then f(n) is O(h(n))
* If f(n) is Omega(g(n)) and g(n) is Omega(h(n))
- Then f(n) is Omega(h(n))
* If f(n) is Theta(g(n)) and g(n) is Theta(h(n))
- Then f(n) is Theta(h(n))
4) Symmetric (5:18)
* If f(n) is Theta(g(n))
- Then g(n) is Theta(f(n))
5) Transpose Symmetric (6:23)
* if f(n) is O(g(n))
- Then g(n) is Omega(f(n))
6) More (7:44)
* if f(n) is O(g(n)) and f(n) is Omega(g(n))
- Then f(n) is Theta(g(n))
THe comment which makes century...
Thankyou sir
At 1:53, if we multiply wd 1000 dn the property will not hold
Sir, i have a question that in the properties of asymptotic notation the third property that is transpose symmetric you told that it is true for big O and big omega so my question is why it is not true for theta?
That property is only concerning big O and big omega.
Hi,bada cute bolta ye band XD
by reflexive property ,can we say that if f(n)=n! then f(n)=theta(n!)??
Every function is both upper and lower bound of itself. There fore it's correct
Reflexive property satisfies for both upper and lower bound right?
yes... f(n)=n^2 ... f(n) is O(f(n)) i.e. O(n^2) ... f(n) is Omega(f(n)) i.e. Omega(n^2)
6:46
What's the difference between Order and Big Oh?
Understood 🤘
Thank you very much for clear explanation 👌
is g(n) just the degree of the polynomial?
Is reflexive property true for all three??
dotnettutorials.net/lesson/properties-of-asymptotic-notations/#:~:text=Reflexive%20Properties%3A,O(f(n)).
yess
Reflexive property is also for Big-Omega and Theta or not?
Yes, valid for upper and average bound too...
In reflexive property if f(n) = 2n+3
Then big O is what only O(n) if yes then how is it reflexive ?
Please reply me sir ?
Abdul Bari yes sir but I am watching from starting video now I am in this video tutorial so can u clear my doubt sir ?
Abdul Bari sir then every function become reflexive but I think f(n) = n has reflexive now the case 2 if f(n) = 2n+3 then reflexive is not possible because here we get only O(n) not O(2n+3) because in asymptomatic notation we take only highest order not entire expression !
Correct me if I am wrong. I guess you have ignored the '3' here as i have seen we do not consider the constant value while writing the expression. The highest value is n, we discard the lower order values when we write the expression. Am i correct?
we ignore constants when we need to find asymptotic notations! So this is correctly O(n)
If u have watched the previous videos then
2*n + 3
how is the reflexive property true for n!
that realization at 8:11 ...
If f (n) = Θ(g(n)), then 2^f (n) = Θ(2^g(n)). Is this true?
Symmetric when only function order same not function same can anybody tell.
Reflexive only valid for theta only.
Please tell I am requesting if any one know
you are god.
Can somebody educate me how these notations helps in coding ??
if function it self is a upper bound of the function and lower bound of the function why can not we write n! is an upper bound of n! and lower bound of n! and then n! belongs to theta(n!)
Cause n! is not a polynomial function. So that's why we use other polynomial functions to represent its upper and lower bound.
hi sir i have a small request for you, if possible please arrange normalization concept in DBMS
please watch knowledge gates for this topic
symmetric was confusing. Do f(n) and g(n) needs to be same ?
Yes
The dominant terms ! so yes they shld be same
6:21
I don't think symmetric property is correct
e.g. f(n) = 2n +5 and g(n) = n
Yes f(n) = theta( g(n) )
but g(n) = theta( f(n) ) = theta ( 2n + 5)
Bro 2n+5 ka thita o n hoga
cool
Common sense properties
great lecture sir, but is it compulsory to having knowledge of mathematics.
I would suggest you to read basic discrete maths
Sir ncube is bigO (upper bound) of n
Actually I didn't understand sir😢 all mix-up nd making me confused 😕
Hi sir,
Can you post the videos on Automata and Compiler Design .
Refer czcams.com/play/PLmXKhU9FNesSdCsn6YQqu9DmXRMsYdZ2T.html
I think someone copied his lecture on Geeks for geeks too 😭😂😂😂
what is the prove of these properties? we are just taking examples and writing them acc to statements. How can we prove them?
Sir! I didn't understand transpose symmetric.
first know what omega notation means it means if f(n) is omega of g(n) then it means f(n) has upper bound on g(n).
Bigo notation means if f(n) is bigo of g(n) then it means f(n) has lower bound on g(n).
and then listen what sir wriiten if f(n) is bigo of g(n) it means f(n) has lower bound on g(n) and g(n) is omega of f(n) means g(n) has upper bound on f(n)
simply... if a number 2 is a smaller quantity compare to 3 then 3 is the larger quantity compare to 2
@@fashionvella730 ulta bolra big-o means function is having upper bound over g(x)
My dout is not clear
(y)