1.10.2 Comparison of Functions #2

[@whitpan]

Mr. Bari, I am a university student in Canada learning computer science. I have just spent several hours watching all of your videos covering the content that has been taught in my current class which I was having a lot of difficulty with. I cannot thank you enough for sharing your amazing skill for teaching and your experience with us students. I am so much more confident in my understanding now and will be doing better in this class and others going forward thanks to you helping me with my fundamentals. Thank you so SO very much.

[@utkarshsingh3275]

@@zeejan9241 creep😒

[@kshitijmathur1358]

I am Rajasthan University grad and have 8 YOE as SE - for 12 years I was afraid of DSA. After watching your videos I realised the literal meaning of the Sanskrit word "Guru - One who dispels the darkness". Please accept my sincerest bow. 🙏🙏

[@enoughgame1006]

Don't bow to human, you can say thanks, bow to only ONE CREATOR

[@suuryaprabhat7051]

Sir One thing i observed in youtube is for stupid jokes number of views and shares are more ... Yours is the best content on algorithms .. I loved your videos i will tell my frnds to share as they can... its a must see video because you came forward to explain us most important concepts in a simple and best way.. You are the best... keep posting sir try to post in theory of computation sir also sir

[@ankityadav-mn5fv]

your clarity of concepts and the confidence with which you explain makes you a wonderful teacher.

[@programmerfresco1850]

The BEST algorithms instructor I have ever seen! He deserves to teach at a top university in the US. Much better than most professors

[@Rishav_Raj17]

Why he deserves to teach in United States. he is good wherever he are. if he teaches in United States only some MITIAN and HARVARD students get in touch with him and we all know that they are already a high knowledgeable students. so sir doesn't need to go some big universities🙄😊

[@usefullyuseless4404]

@@Rishav_Raj17 Agree 100+

[@krishanubanerjee5806]

And this is how we lost the great qualities of India Only for this type of thoughts

[@mahjabinfiza9982]

@@Rishav_Raj17 The commentator was just appreciating his teaching method no need to take everything negatively…

[@advantech_video]

He did teaching at one of college that is affiliated one of good universities ( Osmania University, Hyderabad, TG) in india.

[@hussaini24]

100% better than my 2hours Analysis of Algorithm class. Thanks so much sir.

[@Godson7278]

yes I agree wit you

[@akravi8926]

3:19 now,, don't say they are equal....scolding but funny... perfect sir..I enjoy watching your lecture

[@augusthagedal2050]

I was so close to saying they were equal! Huge jumpscare

[@chiragsachdeva4685]

dear sir, you are the definition of real teacher, although it is just one line, but it is very deep.

[@vibewWithNick]

Sir, you were right, I practiced all of these and I could solve my test problems !! your are great, much much thanx from USA !!

[@vandangorade6738]

Thanks to youtube recommendation algorithm! the best course existed on algorithms!

[@sandeepmandrawadkar9133]

I appreciate the choice of examples you use to clear the doubts! Awesome, thanks from the whole student community world-wide...

[@shank1er]

These videos of yours need to have million of views. the best lessons by far. My professor should look at your videos

[@sirro8047]

Thanks!

[@lukmankhan_]

6:51 G2 is considered greater because it is greater for any element after 10,000 upto infinity but the same can be said for G1 and it will be greater for any element less than 100 upto - infinity.

[@Lucifer-kd1od]

Classy stuff sir! Simply classy! Direct to the point, direct questions and to the point answers. Very much impressed!

[@INDIANSinghX]

He is HC VERMA of ALGO.. super like sirr...

[@behnamseydabadi8819]

I don't know how, but you make hard things very easy and understandable. Thank you.

[@NishaOnYoutube]

Sir Cannot thank you enough . May god bless you and your family.

[@anshul90100]

Sir in 4th case at @8:58 in video after apply log we will get below equation i.e equal so it can be big Oh.... we have 1/2 loglog n =O(loglog n) Please clear this If I am doing wrong... Thanks...

[@sankethb.k642]

You are right

[@tirthdoshi7463]

Exactly

[@oishikachaudhury3718]

You are right. I got the same value too,

[@rahulmallah8306]

I think he said to apply log on both sides. So when you apply log to loglogn, it has triple logs. So logloglogn which is smaller than 1/2 loglogn. So it cannot be big Oh.

[@tashikmoin1168]

thanks @rahul

[@khalidahamed2673]

7:53 In the second relation, 2*(2)^n - in this case we can't ignore 2 as a constant, right? But you did so and proven it as true. Why? It is obviously O(2^(n+1)).

[@hemantbhangale9505]

Excellent progression and crystal clear content. Thanks!

[@akashrawat5735]

Sir, I have doubt 3:45 you are saying that after applying log don't cut off coefficient but in previous video's last example after applying log you told that don't look coefficient, they are asymptotically equal. This is little bit confusing. I think in previous video you forget to told that don't cut off coefficient after applying log..?

[@TruWill99]

He didn't apply log. One side already had log in the function, so he just simplified it using log rules.

[@souvikchatterjee1621]

Sir u are great....ur lectures on algorithm is just beautiful and i've great respect for u....thank u sir for those videos which make me easier to understand that subject.....

[@winter_moon_11]

0:36 why did we say it is base 2? I thought it would be base n since we are using log. When using log base 2 dont we just call it lg? Or did we said base 2 for both f(n) and g(n) but for the f(n) it didnt matter which base it is so we did not specifically write down and for the left one we specified to get rid off the log part?

[@paramitamondal7766]

Your videos are life saver in this lockdown period..

[@bh4541]

dear sir , 1:18 , n^(log n) should be greater than 2^ (root n )

[@jie-i2r]

there maybe exists an error,for (log n)*(log n) cannot be transformed into 2log n

[@picoBeBlack]

This video along with part 1 helped a lot clarifying the comparison of 2 functions. Thank you!

[@VLaxmiNarayanSharma]

2:02 I am getting f(n) greater than g(n) if I substitute values of 4,8,16 for n, please someone tell me if I am correct

[@minhazulislam4682]

0:51 ninja technique to overcome confusion: "keep applying log bois, keep applying log" (imagine I said it like skipper from the penguins of madagascar)

[@nausheensiddiqui8745]

Keep waving boys, keep waving

[@subramaniyanvg6367]

I like the problem of true or false problem very nicely explained sir.

[@AkashKumar-kj1ox]

Dislike by those who has no basic idea of functions Or maybe he is adept in it. Don't demotivate yaar becz of your personal reason. He is doing good. Encourage him. Jai hind👏👏

[@vipingautam1257]

Sir your lectures are wonderful, I must admit the Gate problems you've solved are really helpful to built concept on this..Thanks one again...I am now confident..

[@Shashwat_Tiwari]

When he said don't say equal don't say equal , I got busted virtually.

[@ravitejamadamanchi8665]

sir i got a doubt at 9:15 that how log^2n will become O(2^n)? thanks for the lectures! These lectures are really helps me a lot to prepare for my exams

[@factogenesis]

its only about to greater or less than for order...O(2^n ) is greater...n^logn is order of 2^n

[@anuragsahoo3767]

@@factogenesis can you say how que 3 is done? 2 ^2n= 4^n how ?? 2^2n= may be 2^4 if we take n as 2

[@vennela1103]

@@anuragsahoo3767 yeah even i got the same doubt..

[@felixwang3216]

I have the same question as well.....After 4 yrs.

[@felixwang3216]

Oh! I got it. cuz the question is BIG-O，2^n is greater than log n log n，so it's TRUE here.

[@NigarHusain]

Where have you been all my life.. thanks for detailed explanation

[@zitalabs2435]

Sir, @0:59 log is applied to f(n)=(log^2)n. Then applying log to f(n), f(n)=log(log^2(n)). Afterwards how it got simplified to f(n)=2log(log n)?. Please help

[@shishirbagalkot1068]

It should be log(log n)^2 By mistake he wrote it as log^2 n

[@dbsllama6042]

Shishir Lb it’s not a mistake, both expressions are equivalent. they are simply expressed in different forms

[@johnkrasinski6225]

Its incorrect

[@simranvedpathak7112]

Sir ! at 5:38 in that Q can we consider in this way that time complexity is mainly found for bigger values and therefore g2 >g1

[@houseofphilosophy]

Yours content is the best content on algorithms .. I loved your videos i will tell my frnds to share as they can... its a must see video because you came forward to explain us most important concepts in a simple and best way.. You are the best... keep posting sir try to post in theory of computation sir also sir

[@abhaydeepsharma5027]

Sir I think 2:00 n raise to power logn must be greater than 2 raise to power root(x) ....Check by substituting x=100

[@priyalmaheshwari4008]

Asymptotic comparison tells us how the functions behave for large values of n, but it may not be accurate for small values of n. For small values of n, we need to compare the values of the functions directly.

[@jassi123jassi]

Respected Sir, thank you for great content. sir, kindly refer us the book on algorithms that you have followed.

[@tsts6728]

الله يوفقك ويجزيك خير 🥰 God bless you💙

[@hiteshyadav2298]

at 9:17 why n > (log n * log n ), Because if we take log again then we will get : 2 *(log n) = log n for example if we take n=8 then n will be 8 and log n* log n will be 9 .. so log n * log n > n .. Please correct

[@chandramohannegi]

very very very thanks sir ,,your tuts are having all that a student want to know about the data structure ,you teaches in a very good way ,i was searching for goood data structure tuts thankkssss

[@niantongdong2971]

Thank you for your vide. It is very helpful. I have a problem. In 1.10.1, you said that 2logn is greater than logn so that f(n) is greater than g(n). After that, you also show us a different comparison that f(n) =3n^sqrtn and g(n)=2^(sqrtn log2 n), which is equal with result 3n^sqrtn and n^sqrtn. I am confusing when and how I can determine that if the coefficients are important for the comparison or not. Again, thank you very much for the great presentation.

[@priyalmaheshwari4008]

in the first question he had applied log on both sides so he has to check the coefficient on both sides too. in the second question he did not apply log on both sides but rather used logrithmic formulas to simplify g(n). When we are comparing after applying log that means at that time we have made changes to question therefore we have to take coefficient into consideration but if we have not made any changes to question then we can ignore coeff.

[@sonamchauhan2968]

Thank you so much sir so this valuable content 🥰👍👍

[@arunk8956]

2:23 can anyone clear my doubt please? 2^logn = n right? How come it's logn since 2^logn = n^log2 for the same base 2 right? So the answer will be n instead of log n??

[@MrChuxel]

Left part is n and right part is n^sqrt(n) -> 9 < 729. If we calculate log from left and right than left parts is logn and right part is logn*sqrt(n) if n = 8 -> 3 < 3 * 1.732 - so LEFT < RIGHT

[@simranshah2827]

He’s taken log

[@Truthseeker98-e3k]

sir , at number 4 of true/false in 8:50 If we apply "log" at LHS, then it will be 1/2*loglogn= (loglogn)/2. so it matches with RHS i.e: O(loglogn) if we eliminate the co-efficient 1/2 form LHS. So that, the number four is true i think. PLZ Correct me if i am wrong.

[@shishirbagalkot1068]

When you apply log on both sides on RHS it will become log(log(log(n))) which is smaller than log(log(n))/2 Hope this helps :D

[@Truthseeker98-e3k]

@@shishirbagalkot1068 Oh!! Thanks s lot. You are right.

[@nitismita1035]

I faced the same. Thank u both for raising that n answering.

[@shujamukhtar4563]

At 7:28, why are using theta to prove whether the statement is true or false?

[@vakhariyajay2224]

Thank you very much. You are a genius. 👍👍🙏🙏👌👌🔝🔝

[@karanchandra9789]

1:20 how log square n is equal to 2loglogn after applying log

[@DarthV017]

log square n can also be written as [log n]^2. Now let us take log[(log n)^2], it will give 2 loglog n. Hope it is clear now

[@karanchandra9789]

@@DarthV017 Thank-you 👌

[@SHA256HASH]

@@DarthV017 Beautiful. Thank you!

[@welliguessillbehereforawhi3963]

@@DarthV017 isnt it wrong? that rule only applies when there's a power on the argument of the log NOT the WHOLE log

[@DarthV017]

@@welliguessillbehereforawhi3963 the power of 2 is on the argument of log not the complete log we have exp = (log n)^2 log n = x exp = x^2 now we will take log log(exp) = log (x^2) = 2 log (x) = 2 log(log n) replacing x

[@welliguessillbehereforawhi3963]

How come he took the base as 2 at 0:45? Isn't the base 10? Or it doesn't matter?

[@ManishIcon]

two functions f and g can also be compared using lim n->∞( f/g ) and L'hospital rule.

[@mradul.bhardwaj]

in 1:33, in small values( 2^n^0.5 so won't your ans be wrong after n=8.83

[@sohaibfarooqui6366]

Sir in the first example of this video if we try to put some values like 64, 16 or any other value then n^logn comes out to be greater than 2^√n Please clarify

[@eshankaur9659]

Yeah it's true then which is smaller??

[@Nano-ih3ig]

Try for larger values, n^logn will be less. Tried for 512 and 1024.

[@priyalmaheshwari4008]

Asymptotic comparison tells us how the functions behave for large values of n, but it may not be accurate for small values of n. For small values of n, we need to compare the values of the functions directly.

[@aminulislamrahat3889]

9:15 sir I can't understand how log n * log n is 2^n. cause lon n* log n = (log n)^2 = log n^2 = 2 log n

[@utkarshsingh3275]

Bro You need to learn the basics of log. What u have written is completely wrong.

[@dineshsaini6051]

(log n)^2 is not equal to log n^2. for eg: (log 2)^2 =(1)^2 =1 and log 2^2 = log 4 = 2.

[@AnilKumar-wd3gu]

What about Amortised Analysis....It had included in my Syllabus ..Please Teach them also

[@abdulfattah.hussein]

South Valley University students love you sir ❤❤❤

[@gurupreetsingh8347]

pl make understand this function at 7:45 ..... again in details , how 2 power n+1 = 2 power n ?, can we cut off the 1 ????

[@JourneyMindMap]

in the lower side also g2 is greater because if we square negative values it becomes positive and cube will be still negative. and number 4 & 5 is true because we no need to apply log with in big O

[@kattekolavaishnavi9319]

sir 3^log n and n^log 3 which is asymptotically greater both gives same answer when log is applied?

[@dbsllama6042]

They are equivalent, use the 4th equation for log he wrote in the video

[@chiragsachdeva4685]

good observation brother

[@nitindevella]

sir at last while discussing 2^n+1 = O(2^n), considering 2 functions , if we apply log on them to check which is greater, we get f(n) is greater than g(n), then it has violated sir?, can u please give an explanation for it sir?

[@saurabh7806]

i was also wandring about it if u had found the answer then please reply back!!

[@muhammadmustafamustafa2442]

sir can you just explain that why we are needed to take log for checking the complexity ??

[@bitboyrishi43]

i have a doubt sir at 6:42 , all the values less than 100 g1(n)>g2(n) , it means till -ve infinity lots of values are there where g1(n)>g2(n). now then why g2(n)>g1(n).

[@simranvedpathak7112]

At 5:38 in that Q can we consider in this way that time complexity is mainly found for bigger values and therefore g2 >g1?

[@S2IconVlog]

Amazing teaching

[@hitabratanath305]

Sir, in 2:00 f(n) >g(n)

[@pranitbatra2]

Only for (0,9). But for x >=9, g(n)>f(n)

[@devyadav683]

All of them I have studied in class 12 calculus chapter

[@talha_05]

How did you get log 2 base 2 at 0:38?

[@studyah]

that's the standard base we take in cs

[@krushngor2810]

I am having trouble at 0:51 sec: g(n) = 2^sqrt(n) (apply log) =log [ 2^sqrt(n)] (apply logs 3 property) sqrt(n) = log2 after this I was lost can someone explain that! Thanks for your time in advance!

[@gurupreetsingh8347]

hi sir, in the length of 3:45 as u said after apply log we can't cut off the constant so n is smaller then 2n , but value wise 2n is greater then n but asymptotically they would be equal right ? as u suggested in the just previous video because if we have to right asymptotically ( n and 2n) then the functions would be equal like O(n) ...... So why we can't cut off the constants after applying logs..... ????

[@Rob-J-BJJ]

yes sir

[@chandu798]

We have applied log to get the comparison. In this case there is no need to apply log as we can breakdown the comparison to 2^n and 4^n. So obviously 4^n is greater than 2^n

[@aliadel1723]

I hope you make a course for mathematics ♥

[@sameerkhnl1]

Very well explained. Thank you sir.

[@Egli]

Yet another amazing video

[@aaronaaronaaron5922]

good lord 🚀 You are amazing 👑

[@satyanarayanmohanty3415]

Simply outstanding.

[@HappyKitya]

0:47 2:30 3:19 4:23 6:55 8:07

[@ateequrrehman9466]

sir you perfect teach

[@prateekkumar4728]

sir in second example if we take any value of n then 2^n+1 is greater than 2^n so how it is true

[@jyoshnadeepala6912]

As coefficients can be ignored

[@mksbits]

1:59 log^2n is not equal to log logn....please correct it

[@NB-fx9xe]

I also got the same doubt. Please clarify this.

[@NB-fx9xe]

@@abdul_bari Thanks Abdul. We were always thankful for your knowledge.

[@divyanshutripathy3484]

We can also use differential calculus to compare the functions but i think log is much easier

[@asdfghjkl1770]

A wonderful teacher!

[@samarpitaroy9054]

you're the best sir!!!!

[@Shubhamnayakdubey]

Sir, can we use limit to compare these functions. lim n->∞ f(n)/g(n). If the limit is 0, f(n) grows slower than g(n). if limit is finite and non zero constant C>0, f(n) and g(n) grow at the same rate and If the limit is ∞, f(n) grows faster than g(n).

[@akhilvarma6648]

Hi, can you please explain, how log 2 base 2 came at time stamp- 3:10

[@acceleratorlevel645]

usually we take the base as 2 that is why it is base 2 log 2

[@muhammadmustafamustafa2442]

7:50 why it was correct ??

[@lizavetameta]

Bless this teacher

[@luisz2k]

9:56 "we've finished the 1st chapter of algorithms" chapter 1.11 and chapter 1.12: am i a joke to you

[@vennela1103]

Sir 2^n and 2^2n asymptonically equal to O(n) then at last 3rd question will be true right..according to the order you mentioned..please clarify..!

[@azizalti5015]

May God bless you

[@hill-ar-ious]

In the last True or false question, Can we say that let f(n)=log(n)*log(n) then Theta(f(n))=loglog(n) and O(f(n))=n. So, it's true.?

[@mohammedadel8948]

Thank you , I appreciate your help so much

[@sivasaikrishna246]

sir 2^n+1 is how less than 2^n pls explain.

[@ankitkumain]

Sir, can you tell me difference between algorithm and pseudo code or are they same??

[@AnshuKumar-oj8ww]

Sir if last true or false is correct then first 4 should also be correct.

[@mansisinghal1634]

sirji, how to solve questions such as finding t.c for transitive closure of binary relation,when array is sorted...I mean how to approach such questions?

[@zayphyo1367]

Great explanation sir

[@Sufyansgoals]

After applying the log, you stated that we shouldn't cut off coefficients, can we cut off constants? such as log(n) + 5 and log(n) +2? are they equal asymptotic wise?

[@priyalmaheshwari4008]

yes they would be equal asymptotically

[@juneshgautam8655]

in 0:43 is it log^2 n or (log n)^2?

[@srinivasaraodontiboyena7462]

Both are same

[@abhisheksunkara631]

For True or False, Second one seems False as F(n)>G(n), G(n) cannot be upper bound of F(n). Correct me if i am wrong.

[@sayajinppl417]

Hello question please , if you have f(n) = g(n) then is f(n) O(g(n)) or OMEGA(g(n)) or teta ?

[@swatiraghav5492]

Thanks, Sir, you are fun.