Při používání metody rozděl a panuj se snažíme o dělení problému na menší pod problémy, z jejich výsledků pak skládat výsledek a s menšími problémy naložíme stejně, dokud se nedostaneme k triviálním vstupům.
MergeSort
Kde Merge je metoda slévající v lineárním čase dvě seřazené posloupnosti.
Analýza
bude značit počet kroků algoritmu MergeSort na velkém vstupu.
Rovnici vyřešíme dosazením rekurentní rovnice do rekurentní rovnice a pozorujeme přírůstky.
Master theorem
Věta: Rekurence, ,
tak rekurence má řešení
- pro ,
- pro ,
- pro .
Karatsuba
Rozdělíme každé číslo na dvě poloviny (po cifrách):
Pak:
Tedy:
- místo 4 rekurzivních volání pro součiny: , , ,
- použijeme jen 3: , , a