2.3.2 Recurrence Relation Dividing [ T(n)=T(n/2)+ n]. #2

Recurrence Relation for Dividing Functions
Example : T(n)= T(n/2) + n

solved using Recursion Tree and Back Substitution Method

Courses on Udemy
================
Java Programming

Data Structures using C and C++

C++ Programming

[tyrannicalguy]

In the circle logic, [1/2+1/4+...+1/2^k] = 1 but in the recurrence relation equation, we have T(n) = n [1 +(1/2+1/4+...+1/2^k)] which should be equal to n(1+1) = 2n but n was written instead. Although complexity of the algorithm still remains the same.

[mohsinkhan]

Amazing example, got lot of doubts cleared by that circle example

[urvashisharma]

circle explanation for the sigma expression blew my mind...hats off

[satyamkumar-lfbw]

I want to really thanku from core of my heart. sir U r explaining way is so amazing and effortless...that any one can read it in interesting way..sir I m big fan of ur teaching one of best teacher I have seen ever on Utube.Want to meet U once If it could possible.amazing teacher amazing job...yaar salute sir A big thanku.

[md.nurulabsur]

@3.57 What a way to explain things! Too good!

[nandakumart]

Through circle logic you simplify the calculus problem also😍

[spidermanclips]

he's simply the best have never been this comfortable with algorithm but this guy made everything look so easy and simpler
unlike my uni teacher who can't spell things the right way

[pradeepparsam]

woow... what an explanation with amazing examples, that circle one is superb.

[monalisagupta]

Best Teacher for algo. This was once a difficult subject for me. Thanks for making it simple for me.

[supunmadusanka]

Realy Good Explanation sir Understood very well.

but I found a small error in the explanation, I think the Sumation of 1 + 1/2 + 1/2^2 + 1/2^3 + + 1/2^k is converging to 2
(not 1) because we already add a 1 to that circle explanation you gave. The explanation is correct (Dividing circle explanation ) for
1/2 + 1/2^2 + 1/2^3 + + 1/2^k and it is converging to 1 But in the above series we get for T(n) it is starting from 1 since it is converging to 2

Thank You!!

[subramaniyanvg]

As I see videos in playlist it gets tough and interesting. Very few have teaching skills like you sir. Thanks sir.

[getsomespeed]

U are great sir you are best teacher for algorithm❤

[ashutosh]

the sums is 2 Just by circle analogy you have 1 complete and 1 broken circle

[anshulgoel]

Point to note at 4:11 the value of k is log(n) so it becomes 1/ (2 raise to power log base 2 of n) which is basically n, so it becomes 1/n and hence the sequence is infinite as the number n is assumed to be very large number.

[asmitabari]

Thanks sir!! ... You are really a lifesaver... Your explanation is really good and have covered almost all the examples thoroughly... I am able to solve any example on time complexity or recurrence relation jst watching your videos... 🙂

[mostafatarekadam]

WoW that circle explanation was superb!

[sergeyzolotarev]

Great video, but maybe another option would be using GP series formula for the sum of 1/2^i. The sum is something like 1 - 1/n, not 1 as described in the video. And after multiplication to n we get O(n) eventually.

[WifiLearn]

Gr8 job sir... Only u r the youtuber for best video of Analysis of algo.

[samadhanghorpade]

00:56 Solving Recurrence Relation T(n)=T(n/2)+n
01:52 Understanding the recurrence relation T(n)=T(n/2)+ n
02:48 Discussing the derivation of a specific recurrence relation
03:44 Recurrence relation for T(n) is T(n/2) + n
04:40 Recurrence relation T(n)=T(n/2)+n explained
05:36 Explaining recursive equation T(n)=T(n/2)+ n
06:32 Explaining the recursive relation T(n) = T(n/2) + n.
07:26 Understanding the recursion relation T(n)=T(n/2)+n

[taraj]

won't the sum be equal to 2 at 4:12.