2.3.1 Recurrence Relation Dividing Function T(n)=T(n/2)+1 #1
HTML-код
- Опубликовано: 29 сен 2024
- Recurrence Relation for Dividing Function
Example : T(n) = T(n/2) +1
explained using Recursion Tree and Back Substitution Method
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
![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)
![2.3.3 Recurrence Relation [ T(n)= 2T(n/2) +n] #3](/img/1.gif)
Thank you sir for reducing my time complexity of understanding time complexity !
😊
😂😂😂🤙
@@abdul_bari sir make new videos
😅😅😅😅😂😂
😂😂😂 gold
Wow ! Nobody would have explained better ! Thank you sir ! Hope you make more videos !
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 so much!!
太强了 老师！！！
bro reply in english so that other could understand bcz if u understand this video , u must know englsih
Thank you!! God bless you.
Hats of to you sir awesome explanation .
Very clearly explained sir
very well explained
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)
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, 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)).
Sir! T(n/2)=T(n/2)+1 is this right or T(n)=t(n/2)+1 ?
How can I calculate Theta notation using this method.
shouldn't this be T(n/2)+2 , as if statement also takes 1 unit of time
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
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...
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.
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
The way he teaches is so relatable, no hidden magic, he unfolds everything
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 🙏
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.
Thanks Prof. you are doing awesome job, the way you explain the algorithms , may God bless you
Sir agar meri koi behn hoti to mey apko deta shadi k liye
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.
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)?
The way you explaining sir is just awesome..cleared all my doubts..Thank you very 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 very much. You are a genius. 👍👍🙏🙏👌👌🔝🔝
The textbook I am reading skipped so much material that it is also impossible to figure out without a good explanation. This wa sexcellent.
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)
Plz tell me what happen in case of T(n)=2T(n/2)+nlogn
nlog^2n
explained it way better than sorry ass professors at UNT, thank you!
Thank you sir for helping me understand this difficult subject of Algorithms in a simpler, digestable way :)
7:10 isn't that "k" iteration?
I love your accent, kisses from Brazil!!
3:05 unity value for division and multiplication is 1
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)
This is such an amazing simple explanation. Thankyouuu!! 😊😇
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.?
I am so so grateful for coming across your channel sir.. thank you so much for this comprehensive teaching ❤❤❤
I LOVE YOU !!!
@abdul bari ,U are doing a great job sir
EXCELLENT YAAR EXCELLENT ITS JUST WOW
Sir why can't n
Thank you so much!
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
Sir ..will we use big Oh notation in every question ? Plz answer quickly..
Mostly Ig
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, @5:09 How many steps it is taking ? Shouldn't it be ( k+1 ) ?
Exactly !!!!
But how does it matter
@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
Thank you sir !
T(n)=2T(n/4)+3^1/2 sir i can't solve this question
thankyou sir
Eisai levetnis
¡Gracias!
Sir amazingly explained...... great job sir👍
Lots of Respect!
Thank you sir for clearing my doubt
You are Pro now master theorem look obivious
😍
Thank you , I appreciate your help so much
You are the best thank You for This super course
5:32
IIIT dharwad pppl🙄 like karo
so what is the answer if we put n/2^k =0
where T(n)=0
ok thanks.
T(n) = T(n/2) + log(n). Can I have an explanation for this?
yes we have T(n) =O(n**1/2)
Plzzz solve my pblm and show me
absolute unit !!!! thank you
Sir can I solve it by using master theorem ? Isn't it faster ?
Yes, the answer will still be O(logn)
Thanku so much sir
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.
Sir thank you
a gold mine in youtube
Thank You !
Thank you!
you are GOD !
nice
👍
excellent sir my concepts are very clear thank u so much sir
First Like and then Comment GOD and then watch!!
Time complexity of T(n) =2T(n)+n is 0(2^n) not 0(n2^n)as you have said
Terrific Lectures and the Teacher
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