Masteryhtälöjä
Masteryhtälöitä, eli mestariyhtälöitä, käytetään tietotekniikassa ja algoritmiikassa analysoimaan rekursiivisten algoritmien aikakompleksisuutta. Ne tarjoavat systemaattisen tavan määrittää suorituskyvyn kasvu suhteessa syötteen kokoon. Yleisessä muodossaan masteryhtälö on T(n) = aT(n/b) + f(n), missä T(n) on rekursiivisen funktion suoritusaika syötteelle kokoa n, a on rekursion määrä, n/b on syötteen koko rekursiivisissa kutsuissa, ja f(n) on aika, joka kuluu jakamis- ja yhdistämisvaiheisiin.
Masteryhtälön ratkaisemiseksi on olemassa kolme pääasiallista tapausta, jotka riippuvat f(n):n suhteesta n^(log_b a):in. Ensimmäisessä tapauksessa, jos
Masteryhtälöä voidaan soveltaa moniin yleisiin algoritmeihin, kuten yhdistämisjärjestykseen (merge sort) ja pikajärjestykseen (quick sort). Se yksinkertaistaa