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)
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.
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. 🤗
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.
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...
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
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
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
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)
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.
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.
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
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.
Thanks Prof. you are doing awesome job, the way you explain the algorithms , may God bless you
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. 🤗
Thank you very much. You are a genius. 👍👍🙏🙏👌👌🔝🔝
@abdul bari ,U are doing a great job sir
I love your accent, kisses from Brazil!!
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.
This is such an amazing simple explanation. Thankyouuu!! 😊😇
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...
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
😍
Thank you sir for helping me understand this difficult subject of Algorithms in a simpler, digestable way :)
Lots of Respect!
EXCELLENT YAAR EXCELLENT ITS JUST WOW
Sir amazingly explained...... great job sir👍
You are the best thank You for This super course
Hats of to you sir awesome explanation .
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
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)
Thank you!! God bless you.
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
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 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)
Sir, @5:09 How many steps it is taking ? Shouldn't it be ( k+1 ) ?
Exactly !!!!
But how does it matter
What is the time complexity of this function?
public static float myst (float q, int n){
float e = 0;
if (n
order of n
7:10 isn't that "k" iteration?
3:05 unity value for division and multiplication is 1
absolute unit !!!! thank you
Thank you , I appreciate your help so much
thank you so much!!
I LOVE YOU !!!
Thank you sir for clearing my doubt
very well explained
Thank you so much!
Very clearly explained sir
Thank you sir !
Terrific Lectures and the Teacher
太强了 老师！！！
bro reply in english so that other could understand bcz if u understand this video , u must know englsih
explained it way better than sorry ass professors at UNT, thank you!
¡Gracias!
@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
Thanku so much sir
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)?
excellent sir my concepts are very clear thank u so much sir
Thank you!
a gold mine in youtube
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.?
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.
Plz tell me what happen in case of T(n)=2T(n/2)+nlogn
nlog^2n
Sir ..will we use big Oh notation in every question ? Plz answer quickly..
Mostly Ig
sir while solving using the substitution method why we let k=log(n)?
Sir thank you
thankyou sir
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)
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)).
Eisai levetnis
nice
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
First Like and then Comment GOD and then watch!!
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 :)
How can I calculate Theta notation using this method.
Sir! T(n/2)=T(n/2)+1 is this right or T(n)=t(n/2)+1 ?
Sir why can't n
you are GOD !
👍
so what is the answer if we put n/2^k =0
where T(n)=0
ok thanks.
5:32
Sir can I solve it by using master theorem ? Isn't it faster ?
Yes, the answer will still be O(logn)
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
shouldn't this be T(n/2)+2 , as if statement also takes 1 unit of time
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
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 🙏
T(n) = T(n/2) + log(n). Can I have an explanation for this?
yes we have T(n) =O(n**1/2)
T(n)=2T(n/4)+3^1/2 sir i can't solve this question
Plzzz solve my pblm and show me
Sir agar meri koi behn hoti to mey apko deta shadi k liye
I am so so grateful for coming across your channel sir.. thank you so much for this comprehensive teaching ❤❤❤
Thank You !