A második megközelítés az algoritmusok matematikai elemzésén (analysis of algorithms) alapul, konkrét implementációtól és bemenetektől függetlenül. Ezt a megközelítést egy példa kapcsán, egy számsorozatot összeadó program esetén fogjuk ismertetni:

Az elemzés első lépése a bemenetektől való eltekintés, olyan paraméter vagy paraméterek megkeresése, amely vagy amelyek jellemzők a bemenet méretére. Jelen példában a bemenetet a szekvencia hosszával jellemezhetjük, aminek a jele legyen n. Második lépés az implementációktól való eltekintés, azaz egy olyan mérték megkeresése, amely tükrözi az algoritmus futásiidő-igényét, de nem kötődik egy konkrét fordítóhoz vagy számítógéphez. Az ÖSSZEGZÉS program esetén ez lehetne például a végrehajtott kód sorainak a száma. A mérték részletesebb is lehetne, külön specifikálva az algoritmus által végrehajtott összeadások, értékadások, tömbhivatkozások és elágazások számát. Mindkét esetben megkapjuk az algoritmus által végzett lépések teljes számának a jellemzését a bemenet nagyságának függvényében, amit T(n)-nek fogunk nevezni. Ha megszámoljuk a kód sorait, a példánk esetében az eredmény T(n) = 2n + 2.

Ha minden program olyan egyszerű lenne, mint az ÖSSZEGZÉS, az algoritmusok elemzése triviális lenne. Két probléma miatt a helyzet azért bonyolultabb. Először is, ritka eset olyan paramétert találni, mint az n, amely teljes egészében jellemzi az algoritmus által végrehajtott lépések számát. A legjobb, amivel ehelyett rendelkezhetünk, a legrosszabb esetet jelentő T_legrosszabb(n) vagy az átlagos T_átlag(n) számítása. Az átlag kiszámításához az elemzőnek fel kell tételeznie a bemenetek valamilyen eloszlását.

A másik probléma az, hogy az algoritmusok ellenállnak az egzakt elemzésnek. Ilyen esetben közelítésekre szükséges támaszkodnunk. Azt mondhatjuk, hogy az ÖSSZEGZÉS algoritmus O(n) – avagy nagy ordó n – jelezvén, hogy a mértéke, néhány kis értékű n kivételével, a legtöbb esetben n konstans-szorosa. Formálisan:

T(n) O(f (n)) mértékű, ha T(n) ≤ kf(n) valamilyen k-ra, minden n > n0 esetén.

Az O(n) jelölés az aszimptotikus analízist (asymptotic analysis) jelenti. Külön vizsgálat nélkül azt mondhatjuk, hogy ha n aszimptotikusan közeledik a végtelenhez, egy O(n) algoritmus jobb, mint egy O(n²) algoritmus. Egy egyedi teljesítménymérő adat egy ilyen kijelentést nem tudna alátámasztani.

Az O() jelölés a konstans szorzóktól eltekint, emiatt kevésbé precíz, viszont könnyebb használni, mint a T()-t. Így például egy O(n²) algoritmus egy O(n) algoritmusnál hosszú távon mindig rosszabb lesz, azonban ha a két algoritmus T(n² + 1) és T(100n + 1000), akkor az O(n²) algoritmus n ≤ 110-re jobb lesz.

E hátránya ellenére az aszimptotikus elemzés az algoritmuselemzés legelterjedtebben használt módszere. Ez azért van így, mert az elemzés mind a műveletek egzakt számától (a k konstans tényezőt figyelmen kívül hagyva), mind a bemenet egzakt tartalmától (csupán n nagyságát figyelembe véve) elvonatkoztat. Ily módon az elemzés matematikailag kivitelezhetővé válik. Az O() jelölés jó kompromisszum a precizitás és a könnyű elemzés között.

Az algoritmusok elemzése és az O() jelölés lehetővé teszi, hogy egy konkrét algoritmus hatékonyságáról nyilatkozzunk. Arról azonban nem tudunk mondani semmit, hogy az adott problémához van-e nála jobb algoritmus. A bonyolultságelmélet (complexity analysis) területe nem az algoritmusokat, hanem inkább a problémákat elemzi. Az első nagy szakadék a polinom időben megoldható és a polinom idejű megoldást nélkülöző problémák között van, akármilyen algoritmust is használnánk. A polinom idejű problémák osztályát – azokét, amelyek O(n^k) időben oldhatók meg valamilyen k esetén – P-vel jelöljük. Ezeket néha „könnyű” problémáknak hívjuk, mert az osztályhoz O(logn) és O(n) futási idejű problémák is tartoznak. Idetartoznak azonban O(n¹⁰⁰⁰) problémák is, a „könnyű” elnevezést tehát túlságosan szó szerint venni nem lehet.

A problémák másik fontos osztálya az NP osztály, a nemdeterminisztikus polinom idejű problémák osztálya. Egy probléma akkor tartozik ide, ha létezik egy algoritmus, ami polinom időben meg tud találni egy megoldást, és még ellenőrizni is tudja, hogy a megtalált megoldás korrekt-e. Az ötlet az, hogy ha tetszőlegesen nagyszámú proceszszorral rendelkezünk ahhoz, hogy az összes sejtést egyszerre próbáljuk ki, vagy pedig ha szerencsések vagyunk, és mindig elsőre eltaláljuk a helyes megoldást, az NP probléma P problémává válik. A számítógépes tudomány egyik nagy nyitott kérdése az, hogy az NP osztály ekvivalens-e a P osztállyal akkor, ha nélkülözzük a végtelen processzorhalmaz, illetve a mindentudó sejtés luxusát. A legtöbb számítógépes szakember meg van győződve arról, hogy P ≠ NP, vagyis, hogy az NP problémák inherens módon nehezek, és nincsenek számukra polinom idejű algoritmusok. Ezt azonban még soha sem bizonyították be.

Akik a P = NP eldöntése iránt érdeklődnek, azok figyelmébe az NP osztály egy alosztályát, az NP-teljes (NP-complete) problémák alosztályát ajánljuk. A teljes szó itt a „legvégsőt” jelenti, és az NP osztály legnehezebb problémáit jelöli ki. Azt bebizonyították már, hogy vagy minden NP-teljes probléma P-ben van, vagy egyik sem. Emiatt ez az osztály elméletileg érdekes, de gyakorlati jelentősége is van, mert sok fontos problémáról tudjuk, hogy NP-teljes. Egy lehetséges példa a Boole-kifejezések kielégíthetőségének problémája: egy adott logikai kifejezés esetén létezik-e az ítéletváltozóinak olyan logikaiérték-hozzárendelése, hogy a kifejezés igaz legyen? Hacsak egy csodának nem leszünk tanúi, és a P = NP nem lesz igaz, nincs olyan algoritmus, amely minden kielégíthetőségi problémát polinomiális időben megold. Az MI azonban jobban érdekelt abban, hogy vajon léteznek-e hatékony algoritmusok tipikus, előre rögzített eloszlásokból sorsolt problémák esetén. Ahogy ezt a 7. fejezetben láttuk, vannak olyan algoritmusok, mint a WALKSAT, amelyek sok probléma esetén egészen jól teljesítenek.

A co-NP osztály az NP komplemense abban az értelemben, hogy minden NP-beli döntési probléma esetén létezik egy neki megfelelő co-NP-beli probléma felcserélt „igen” és „nem” válaszokkal. Tudjuk, hogy a P mind az NP, mind a co-NP osztályok részhalmaza, és azt gondoljuk, hogy vannak olyan co-NP-beli problémák, amelyek P-nek nem elemei. A co-NP osztály legnehezebb problémái a co-NP-teljes problémák.

A #P osztály az NP-beli döntési problémáknak megfelelő számlálási problémák halmaza. Döntési problémáknak igen-nem a megoldásuk: például létezik-e megoldása ennek a 3-SAT mondatnak? A számlálási problémáknak egész számok a megoldásaik; mennyi megoldása van ennek a 3-SAT mondatnak? Egyes esetekben a számlálási probléma a döntési problémánál sokkal nehezebb. Így például annak az eldöntése, hogy egy páros gráfhoz létezik-e egy tökéletes párosítása O(VE) idejű (ahol a gráfnak V csúcsa és E éle van). A „hány tökéletes párosítása létezik egy konkrét páros gráf esetén” számlálási probléma viszont #P-teljes, amin azt kell érteni, hogy legalább olyan nehéz, mint a #P-beli problémák bármelyike, és így legalább olyan nehéz, mint az NP-beli problémák bármelyike.

A P-TÁR – a polinom-tárigényű – problémák osztályát szintén tanulmányozták még nemdeterminisztikus gép esetén is. Az az általános vélekedés, hogy a P-TÁR-nehéz problémák az NP-teljes problémáknál nehezebbek, bár kiderülhet, hogy NP = P-TÁR, mint ahogy az is kiderülhet, hogy P = NP.