same

Ek baar Reddy sir se padh k dekho.

I think it is a simplification to get rid of the log_4(n) factor in the exponent of the result you get when you use the geometric sum formula. It is just a way to bound it (from above).

Kuch bhi ? master method is easy peasy.

because this picture is missing a little bit of data, at node one as you can easily see we start at n/4. thus T(n/4) = (n/4)^2. (we get this from the n^2 term) this represents the first step whilst it shows and looks like 3n/4 it's actually 3T(n/4) so do the math at the first part of this tree n/16 + n/16 + n/16 = 3n/16 next step is T(n/16) this results in (3n/16)^2 = 9n/16^2 this gives us the sum formula of (3/16)^i * n^2 *c once again look at the tree n/4 n/4 n/4 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 what's implied is: (n/4)^2 + (n/4)^2 + (n/4)^2 = 3n/16 at step one =(n/16)^2 + (n/16)^2 + (n/16)^2 , (n/16)^2 + (n/16)^2 + (n/16)^2 , (n/16)^2 + (n/16)^2 + (n/16)^2 again the reason you square is because the function seems to be order of n^2 at step two this results in: (3/16)^2 = total of 9 n^2 / 256 at next step: (3/16)^3 so on and so forth you get the idea (3/16)^n your confusion as well as mine initially must be from the part where he shouws step one with n/4 *cn^2 the right side should say 3/16*cn^2 and the step two where he has n/16*cn^2 should say (3/16)^2*cn^2

Based on my textbook and explanations from my professor, I think you're right and that this video is incorrect.

You mean 3 times (n^2)/16. And so on

❤️❤️ it's amazing

ya right it's giving dam deep knowledge.

k is the depth of the tree and the geometric series which we get is the end until it becomes one so we considered that it is till infinity there is a difference bro

answer still same, the reason you floor it is to account for odd number n's so its a fine technical detail that gets lost in the big O notation. I wish i understood it well enough to explain but I dont so trust me, you can ignore all floor and cieling notations here.

For time complexity, we always consider large input size. So n is large here. So no of terms log(n) base 3 is also large. So there are large no of terms(almost infinite for large n).

THIS IS A GUESS BY A CLUELESS ALGORITHMS STUDENT: I think it was disregarded because the growth rate provided by the depth is less than the growth rate provided by the series summation. If anyone has a better answer please reply because I'm worried about my midterm coming up!

actually here we assumed that series is infinite but what happens really is that we go till the height of the tree. But it is very hard to solve so we assume this as an infinite gp. 😀

Glad it was helpful!

@@GATEAppliedCourse sir why it is theta of n^2 why not big O ?

In the recurrence relation: cn^2 is nothing but the time taken to combine the divided parts into one. Now if we look at this part where each problem was divided into n/64. When we put n = n/16 we get from the recurrence equation that each part of the n/16th sub problem is divided into (1/16)*(n/4) i.e. n/64. Further we require c*(n/64)^2 (i.e. after putting n = n/16) time to convert these n/64 sub problems into n/16 problem. hope it helps. If not reply.

Wacom tablet

It's been 5 months, but answering it for others... In this we exclude the time complexity due to 7/6T(n/7) as time consumed is less compared to 8/6T(6n/7). So the final answer will include the time complexity due to 8/6T(6n/7)

same

Whatever an actual algorithm does which implements this recursion: the "missing" part is obiously not needed anymore for the solution. A quarter gets *removed* so to say because it is irrelevant to what the algorithm is doing. The sum of the subproblems must not be equal to n. The equation tells you, what value T(n) is going to have if you insert n into function T (T(n) is a notation for: Function T applied on value n). Think of it like any other function f: X->Y with f(x) = y. x is not nessecarily equal to y, but the function f applied on x is exactly y!

Ink2Go

Yes, it is. This course is based heavily on Introduction to Algorithms by CLRS as we mentioned at the at the very beginning of this course.

Yes you're wrong. He added the terms at each level manually into a series so there's no point in multiplying with log4(n). For example if you have to add 1,2,3,4 ; after doing 1+2+3+4, you don't need to multiply it with the number of terms.

nevermind LOL

suppose that a(n) is a geometric serial with constant "r" , we use S(n) = a(1).(1 - r^n)/(1 -r)

n might be infinite though, right?

its a convergent series.A convergent series may have an infinite number of terms but will always converge to a finite value.

You can also use big O instead of theta. If something is both O(n) and theta(n) it means its an asyptotically tight bound, which is the goal when finding a bound. If its not clear what I mean, consider this: everything that is O(n) is also O(n^2) and O(n^3) and O(n^4) and everything that is asymptotically larger than O(n), but O(n) is the bound you choose because it is the closest bound to the function at hand. How do you know if your bound is the closest? It will have the same theta and big O bound (in my example, that would be O(n) and theta(n)).

he never says it's equal to cn²! He says the problem of n is broken into three parts of size n/4 PLUS cn²! It's right there in the equation and he keeps saying our three-part subproblems must be *combined with* cn². If you do not listen closely enough you'll have problems with other resources as well! ;)

@@Kirmeins its very nice and respectful of you to explain him, answer him and help him clear his doubts. But your reply was a little abrasive.

cn^2 is the time that takes to 'merge' the subproblems. And that is why T(n/4) = 3T(n/16) + c(n/4)^2 takes for each 3 subproblems c(n/4)^2 times 3 ===> 3/16 * cn^2.

Its 4^3 not 16^2

@Neel Rayal I think O(n²) < O(n²logn)

Have you taken this question from any sources? I am wondering How can I break a problem of n into 2 problems of size (n-1) each recursivly and again n/2 ? and combine it with O(n) time??

imagine you have an array of size 4 and now according to your recurrence equation, it will be divided in 3,3,2 Can this be a case?

same here