Når vi skal løse et problem, og når mange måder er tilgængelige for at løse dette problem (f.eks.

analyse af algoritmer betyder at estimere deres kompleksitet i asymptotisk forstand. Udtrykket” analyse af algoritmer ” blev opfundet af Donald Knuth. Analyse af algoritmer er bestemmelsen af mængden af tid og rumressourcer, der kræves for at udføre den.

de fleste af algoritmerne er rekursive, de bruger divide og erobre strategien. Den rekursive algoritme kalder sig for de andre input. Det er normalt en del af det oprindelige input, men har en mindre størrelse (underproblem). Der er mange måder at løse gentagelsesforholdet på. De er som følger:

1. Master sætning

2. Gentagelse træ metode

3. Substitutionsmetode

4. Ændring af variabel metode

blandt alle disse metoder er mastersætningen den hurtigste metode til at finde funktionens tidskompleksitet. Det er meget let at forstå og let at anvende. Vi skal bare huske nogle tilfælde. Så her går vi.