You are absolutely amazing! For so long, I never understood how to do anything related to analysis of algorithms, but now I understand! Thank you so much for spending time with us to teach me what other professors have failed to do.
01:06 Dividing functions call themselves for n by 2 02:12 Recurrence relation T(n) = T(n/2) + 1 explained 03:18 Recursion tree method for T(n) 04:24 Reaching the base case of the recurrence relation T(n)=T(n/2)+1 05:30 Algorithm time complexity is O(log n) 06:36 Solving recurrence relation using substitution method 07:42 Analyzing the recurrence relation T(n) 08:41 Recurrence relation T(n) = T(n/2) + 1 results in Θ(log n)
Wow, I loved the way I paused the video and did the substitution method and as well as tree method. Your way of teaching, making it easier and easier for all of us. Thank you so much, Sir.
hello sir u are my Idol , we students will never gets an teacher like you . you are Gr8 sir , I am personally Very Big fan of u . if any Moment of life I want to meet you . I competed your DS course on Udemy on limited period of time & Begin with algorithm course . Sirr One and only last request from you if possible , plz make an DSA problems Sheet with link of your solving Ans & give Related Question As HomeWork . THen Onwards yours course is fully completed And we students Gets fully Prepared for Product Based Company. if the DSA sheet is created By [ Abdul Bari sir. ] , I Gaurented all your Lovingly Students gets Happy and Thankuable for ur Favour. Thank You Very Much Sir. 🤗
Sir thank you for sharing this video...sir can you put video for 1. T(n)=T(n/2)+1. Where n=2↑k for all k greater than or equal to 0... 2. T(n/3)+T(2n+3)+cn. Where c is constant & n is input size... please sir help me...
Thank you, sir, your videos are very helpful for me, I have seen many videos but now to see your videos my doubt is clear and understood the time complexity.
Thank you very much, sir, for such a simple straight explanation. I am getting problem while solving T(n)= T(n/4)+ C. The last step I obtained is 4C+T(n/2^8). how to solve next pl.guide. Pl. don't change the speed.this is required for other stream's students.
Hi sir, I hope you're fine. I just have a question please; when you finish your calculation, you find that "K= log n #base 2#" But when you write the complexity of time, you just write "O(log n) #without a sign to the base#" Is that right? because it may refer to any "base", or maybe because adding the"base" to complexity does not change anything, or the change is not that important. I just want you, if you want please, to tell me the reason behind that. have a good day Mr. Abdul Bari
Sir your lectures are very much easy to understand and also very helpful for gate exam . I request you to upload some java tutorial videos ,especially Java Collection
if the recurrence relation was instead T(n)=2T(n/2) +1, at the base step, would be equivalent to 2^k T(n/2^k) +k right? If so, would that simply into n(1) +logn making this big theta(n)?
@@shubham3079 Try recursive tree method. In the first iteration, the time will be n and in the second iteration, Time will be (7/8)n and then (7/8)^2*n and so on. We can see the pattern as n*(7/8)^k. So the T(n) will be n+((7/8)^1)n+((7/8)^2)n+....+((7/8)^k)n. Take n as common and form a geometric series like n[1+(7/8)+(7/8)^2+(7/8)^3+....+(7/8)^k]. It is equal to n[(7/8)^k]
Now,T(n) will be 1 only if n=1...Note:n cannot be 0 here because of T(n/2),T(n/4) and if n==0, n/2^k=0 which gives our n as zero value. So go with n=1. In the given question ,the highest term is (n/8). So T(n)=1 when n/8^k =1 . Therefore k= log(base8)n.We will get T(n)= n[(7/8)^k].WKT n/8^k=1. So,T(n)=7^k which upon applying k value becomes T(n)=7^log(base8)n. Hence the value big-Oh(7^(logn)).
Why are we using T(n) = 1 when n = 1. In previous videos we used, T(n) = 1 when n = 0. So I was wondering how did you figure out which value of n gives T(n) = 1?
This video is for deviding function . In division and multiplication unit or least value is 1. But in addition and subtraction unit value is 0. For previous cases (addition and subtraction functions) we could assign constant for 0 /unit value. Since sir said he prefer to assign 1 since it is also a constant. When we calculating time compexity all the constants can consider as same even though value is different :)
Sir on starting of ur video the first questions sol is big oh(log n) but i have a doubt thay why big oh..why not omega because log n comes in lower bound as per previous videos.. Sir plzz do rply.. I got stucked here
![2.3.2 Recurrence Relation Dividing [ T(n)=T(n/2)+ n]. #2](http://i.ytimg.com/vi/XcZw01FuH18/mqdefault.jpg)
![2.3.2 Recurrence Relation Dividing [ T(n)=T(n/2)+ n]. #2](/img/tr.png)
Thank you sir for reducing my time complexity of understanding time complexity !
😊
😂😂😂🤙
@@abdul_bari sir make new videos
😅😅😅😅😂😂
😂😂😂 gold
The way he teaches is so relatable, no hidden magic, he unfolds everything
You are absolutely amazing! For so long, I never understood how to do anything related to analysis of algorithms, but now I understand! Thank you so much for spending time with us to teach me what other professors have failed to do.
01:06 Dividing functions call themselves for n by 2
02:12 Recurrence relation T(n) = T(n/2) + 1 explained
03:18 Recursion tree method for T(n)
04:24 Reaching the base case of the recurrence relation T(n)=T(n/2)+1
05:30 Algorithm time complexity is O(log n)
06:36 Solving recurrence relation using substitution method
07:42 Analyzing the recurrence relation T(n)
08:41 Recurrence relation T(n) = T(n/2) + 1 results in Θ(log n)
Wow, I loved the way I paused the video and did the substitution method and as well as tree method. Your way of teaching, making it easier and easier for all of us. Thank you so much, Sir.
Wow ! Nobody would have explained better ! Thank you sir ! Hope you make more videos !
The way you explaining sir is just awesome..cleared all my doubts..Thank you very much sir.
You are my Yoda of the computer science force
AAPKA NAAM KAISE BOLU MAI KUCH SMJ NAHI AARA. IS SE ACHE TO BIOLOGY MAI SCIENTIFIC NAMES HOTE HAI BHAI.
THANKS AND REGARDS
SEXY CHANTU
Thanks Prof. you are doing awesome job, the way you explain the algorithms , may God bless you
Thank you very much. You are a genius. 👍👍🙏🙏👌👌🔝🔝
I love your accent, kisses from Brazil!!
hello sir u are my Idol ,
we students will never gets an teacher like you .
you are Gr8 sir , I am personally Very Big fan of u . if any Moment of life I want to meet you .
I competed your DS course on Udemy on limited period of time & Begin with algorithm course .
Sirr One and only last request from you if possible , plz make an DSA problems Sheet with link of your solving Ans & give Related Question As HomeWork .
THen Onwards yours course is fully completed And we students Gets fully Prepared for Product Based Company.
if the DSA sheet is created By [ Abdul Bari sir. ] , I Gaurented all your Lovingly Students gets Happy and Thankuable for ur Favour.
Thank You Very Much Sir. 🤗
Sir thank you for sharing this video...sir can you put video for
1. T(n)=T(n/2)+1. Where n=2↑k for all k greater than or equal to 0...
2. T(n/3)+T(2n+3)+cn. Where c is constant & n is input size... please sir help me...
This is such an amazing simple explanation. Thankyouuu!! 😊😇
Thank you sir for helping me understand this difficult subject of Algorithms in a simpler, digestable way :)
Thank you, sir, your videos are very helpful for me, I have seen many videos but now to see your videos my doubt is clear and understood the time complexity.
@abdul bari ,U are doing a great job sir
The textbook I am reading skipped so much material that it is also impossible to figure out without a good explanation. This wa sexcellent.
You are Pro now master theorem look obivious
😍
Sir amazingly explained...... great job sir👍
EXCELLENT YAAR EXCELLENT ITS JUST WOW
Thank you very much, sir, for such a simple straight explanation.
I am getting problem while solving T(n)= T(n/4)+ C. The last step I obtained is 4C+T(n/2^8). how to solve next pl.guide.
Pl. don't change the speed.this is required for other stream's students.
@@@abdul_bari Thank you so much sir. is T(n)= log n
O(log n)
What is the time complexity of this function?
public static float myst (float q, int n){
float e = 0;
if (n
order of n
sir, I'm so confused, what is the meaning of 1 step of each dividing !! and the level of the tree please these word are really frustrating
Lots of Respect!
You are the best thank You for This super course
Hi sir, I hope you're fine.
I just have a question please;
when you finish your calculation, you find that "K= log n #base 2#"
But when you write the complexity of time, you just write "O(log n) #without a sign to the base#"
Is that right? because it may refer to any "base",
or maybe because adding the"base" to complexity does not change anything, or the change is not that important.
I just want you, if you want please, to tell me the reason behind that.
have a good day Mr. Abdul Bari
have you got answer ?
Have Same doubt.
Thank you!! God bless you.
Hats of to you sir awesome explanation .
7:10 isn't that "k" iteration?
Sir your lectures are very much easy to understand and also very helpful for gate exam .
I request you to upload some java tutorial videos ,especially Java Collection
if the recurrence relation was instead T(n)=2T(n/2) +1, at the base step, would be equivalent to 2^k T(n/2^k) +k right? If so, would that simply into n(1) +logn making this big theta(n)?
Sir, @5:09 How many steps it is taking ? Shouldn't it be ( k+1 ) ?
Exactly !!!!
But how does it matter
3:05 unity value for division and multiplication is 1
Thank you , I appreciate your help so much
Thank you so much!
Thank you sir for clearing my doubt
I LOVE YOU !!!
sir while solving using the substitution method why we let k=log(n)?
thank u! I was forgetting to count my O(1) steps in the recurrence relation lol, I was like ain't no way this algorithms is O(1)
@Abdul Bari Sir how to solve T with two variables ? For example T(x, y) = Θ(x) + T(x, y/2) , T(x, c) = Θ(x) for c ≤ 2, T(c, y) = Θ(y) for c ≤ 2
absolute unit !!!! thank you
thank you so much!!
Thank you sir !
太强了 老师！！！
bro reply in english so that other could understand bcz if u understand this video , u must know englsih
In the function, if we would take printf() 3 times, then would it be like T(n)=T(n/2)+1 T(n)=T(n/2)+3?? cause we are assuming the printf() line as 1.?
Sorry to bother you sir (and thanks for the great videos), but for T(1)=0 what's the solution? O(1)?
yes 0 is constant so T(1) is O(1)
Plz tell me what happen in case of T(n)=2T(n/2)+nlogn
nlog^2n
¡Gracias!
Sir ..will we use big Oh notation in every question ? Plz answer quickly..
Mostly Ig
explained it way better than sorry ass professors at UNT, thank you!
Thank you for the video, I just have one question: if the function was returning Test(n/2)*Test(n/2), what would be the time complexity of that line?
Abdul Bari thank you. Can I email you one question which is based on this?
Thank you sir, didn't find your email so I have sent the problem on your Facebook page. Please check on Fb messenger.
very well explained
Very clearly explained sir
excellent sir my concepts are very clear thank u so much sir
Thanku so much sir
sir, i'm having trouble solving this question :-
T(n) = T(n/2) + T(n/4) + T(n/8) + n
please give me a hint sir.
Yes sir please make a video on it.
ans: big-oh( 7^ log(base8)n )
@@damonsalvatore8644 please explain
@@shubham3079 Try recursive tree method.
In the first iteration, the time will be n and in the second iteration, Time will be (7/8)n and then (7/8)^2*n and so on. We can see the pattern as n*(7/8)^k. So the T(n) will be n+((7/8)^1)n+((7/8)^2)n+....+((7/8)^k)n. Take n as common and form a geometric series like n[1+(7/8)+(7/8)^2+(7/8)^3+....+(7/8)^k].
It is equal to n[(7/8)^k]
Now,T(n) will be 1 only if n=1...Note:n cannot be 0 here because of T(n/2),T(n/4) and if n==0, n/2^k=0 which gives our n as zero value. So go with n=1. In the given question ,the highest term is (n/8). So T(n)=1 when n/8^k =1 . Therefore k= log(base8)n.We will get T(n)= n[(7/8)^k].WKT n/8^k=1. So,T(n)=7^k which upon applying k value becomes T(n)=7^log(base8)n. Hence the value big-Oh(7^(logn)).
Why are we using T(n) = 1 when n = 1. In previous videos we used, T(n) = 1 when n = 0. So I was wondering how did you figure out which value of n gives T(n) = 1?
This video is for deviding function . In division and multiplication unit or least value is 1. But in addition and subtraction unit value is 0. For previous cases (addition and subtraction functions) we could assign constant for 0 /unit value. Since sir said he prefer to assign 1 since it is also a constant. When we calculating time compexity all the constants can consider as same even though value is different :)
Thank you!
Terrific Lectures and the Teacher
Sir why can't n
Sir thank you
Sir, you mention in binary search algorithm time complexity same equation but there was your answer is that logn but here is log2n.Pls guide me
thankyou sir
a gold mine in youtube
Sir! T(n/2)=T(n/2)+1 is this right or T(n)=t(n/2)+1 ?
Eisai levetnis
nice
you are GOD !
so what is the answer if we put n/2^k =0
where T(n)=0
ok thanks.
How can I calculate Theta notation using this method.
Sir can I solve it by using master theorem ? Isn't it faster ?
Yes, the answer will still be O(logn)
First Like and then Comment GOD and then watch!!
👍
shouldn't this be T(n/2)+2 , as if statement also takes 1 unit of time
5:32
T(n) = T(n/2) + log(n). Can I have an explanation for this?
yes we have T(n) =O(n**1/2)
Charan kaha hai prabhu ,Ek bar mere DAA ke teacher ko dikha aau sayad kuchh sikh le..
@@abdul_bari jokes aside , thank you so much sir For putting Such an effort and making it free for us , saved my semester 🙏
Sir on starting of ur video the first questions sol is big oh(log n) but i have a doubt thay why big oh..why not omega because log n comes in lower bound as per previous videos.. Sir plzz do rply.. I got stucked here
@@abdul_bari so here I can use omega also or only oh and theta
@@abdul_bari thnku soo much sir ur videos r really very helpful
T(n)=2T(n/4)+3^1/2 sir i can't solve this question
IIIT dharwad pppl🙄 like karo
Time complexity of T(n) =2T(n)+n is 0(2^n) not 0(n2^n)as you have said
Sir agar meri koi behn hoti to mey apko deta shadi k liye
Plzzz solve my pblm and show me
I am so so grateful for coming across your channel sir.. thank you so much for this comprehensive teaching ❤❤❤
Thank You !