0
$\begingroup$

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.

enter image description here

enter image description here

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:

enter image description here

The master theorem has $f(n)$ instead of $cn^\beta$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Evil
    Commented Sep 8, 2019 at 1:38
  • $\begingroup$ This is the master theorem. $\endgroup$
    – Yuval Filmus
    Commented Sep 8, 2019 at 16:38
  • $\begingroup$ 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" $\endgroup$
    – AndrewM
    Commented Sep 8, 2019 at 16:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Sep 8, 2019 at 16:40
  • $\begingroup$ 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. $\endgroup$
    – AndrewM
    Commented Sep 8, 2019 at 16:42

2 Answers 2

Reset to default
0
$\begingroup$

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.

enter image description here

Improve this answer
$\endgroup$
0
$\begingroup$

$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.]

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.