0
$\begingroup$

In my slides for my algorithms class, I have a method of finding 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 an 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$.

$\endgroup$
  • $\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 Sep 8 at 1:38
  • $\begingroup$ This is the master theorem. $\endgroup$ – Yuval Filmus Sep 8 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 Sep 8 at 16:39
  • $\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 Sep 8 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 Sep 8 at 16:42
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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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