- Miért O(n^2) a beszúró rendezés futásideje?

Majd a fél vége felé a beszúró rendezés pszeudókódját is átnézzük, abból is látszik, hogy két egymásba ágyazott for ciklus fut, mindkettő n-el arányos, ebből már sejthető az O(n^2).

A rendezetlen tömbön végig kell mennünk (n iteráció) és mindegyik lapnak meg kell találnunk a helyét a rendezett tömbben. A legrosszabb esetben minden iterációban végig kell néznünk az egész rendezett tömböt. Ez 0+1+2+...+(n-1) összehasonlítást jelent összesen legrosszabb esetben. 0+1+2+...+(n-1)=n(n-1)/2=O(n^2)