# Help with Linear recurrence relation with balanced partition

In my slides for my algorithms class, I have a method of finding the complexity of recursive functions called Recurrence Relation with "partizione bilanciata" which means "balanced partition".

My course is in Italian and looking online in English I could not find any trace of this method, I know of the recursive tree, induction, and master theorem.

Has anyone any idea of how this is called in English? I don't like studying in Italian and I do not understand those pdfs.

I'm attaching some images of the formulas.  What exactly "balanced partition" mean, does it have something to do with for example Quick Sort, when you choose a middle pivot and the partitions are equal in size, which means it's balanced?

Is it the same as master theorem written maybe in a different way? I can see the form of the recurrence relation is different than the master theorem: The master theorem has $$f(n)$$ instead of $$cn^\beta$$.

• It seems that part of your questions is more connected to language than Computer Science. Have you tried reading article at Wikipedia and changing language to gather vocabulary? Have you tried reading about master theorem in existing questions at this site?
– Evil
Sep 8, 2019 at 1:38
• This is the master theorem. Sep 8, 2019 at 16:38
• Yes, exactly, when we have a problem divided in subproblems, but my teacher is showing it in a different way , as you can see in my answer on the bottom of the page, so i got confused because she calls it "Balanced partition method" Sep 8, 2019 at 16:39
• It's exactly the same as the master theorem. If anything, the master theorem is a bit more general, since we can replace $cn^\beta$ with any function which is $\Theta(n^\beta)$. But otherwise, it's exactly the same. Just a different name. Sep 8, 2019 at 16:40
• Yes, my confusion comes from the fact that my teacher uses "Master theorem" for the Master theorem for decreasing functions T(n-1) and then she uses, Recurrence relation with "balanced partition" for the master theorem with dividing functions T(n/b) where b>=2. This is why I got very confused, because I studied by myself in English and then I went and looked at the Italian slides and got lost. Thank you for your help. Sep 8, 2019 at 16:42

Looks like I learned it by myself in a different way than my teacher teaches it, and that is why I never heard of "balanced partition".

Apparently it means that a problem is divided in more sub problems (kind of like quick sort as I said), and when we have this condition where T(n/b) and b>=2, we use the "balanced partition" method.

I learned it in a different way, by getting Theta as f(n) and looking for p and k, where Theta(n^k * log^p(n)) , after that I have different cases, like in the following picture, my teacher teaches in a different way and that is why i got confused, because in English there is no "balanced partition" therm. $$aT\left(\dfrac nb\right)$$ clearly indicates that $$a$$ subsets of equal size $$\dfrac nb$$ are processed. For instance in dichotomic search, $$a=1$$ and $$b=2$$. In MergeSort, $$a=b=2$$.

Partitions are indeed called balanced when the subsets are of equal size. The same term is used with trees and subtrees.

[More generally, it suffices that the ratio of the sizes does not get smaller than a known positive constant. This is the case for instance in the "Median of medians" algorithm for linear-time median search. This works because the size of the subproblems tends to one geometrically, hence in a logarithmic number of steps.

In QuickSort, such a lower bound of the ratio cannot be guaranteed, hence its possible $$O(n^2)$$ degeneracy.]