Ratkaisu O(f) on niiden funktioiden g (luonnollisilta luvuilta reaaliluvuille) joukko, joille pätee: on olemassa positiiviset vakiot c ja n0, joilla g(n) =< c*f(n) kun n >= n0. (Monet olivat havainnollistaneet tätä vastaavalla kuvalla kuin luentomateriaalissa; tällöin olisi tietysti hyvä jos kuva ja sen selitys eivät olisi ristiriidassa keskenään...) Ylläolevasta määritelmästä seuraa mm., että jos S on O(f) ja T on O(g), niin S + T on O(max {f, g}); jos S on O(f) ja T on O(g), niin ST on O(fg); jos f on O(g) ja g on O(h), niin f on O(h). Jonkin funktion g kuuluminen luokkaan O(f) tarkoittaa siis, että g(n) on korkeintaan suuruusluokkaa f(n), tarpeeksi suurilla n:n arvoilla. Käyttö algoritmien aikavaativuuden analysoinnissa: algoritmin aikavaativuus ilmaistaan yleensä syötteen "monimutkaisuuden" funktiona. Monimutkaisuus voi tarkoittaa esim. syötteen pituutta tai tietorakenteessa olevien alkioiden määrää. Funktioluokkia O(f) käytetään ilmaisemaan algoritmin aikavaativuuden suuruusluokan ylärajaa. Yläraja ei ole välttämättä tiukka: esimerkiksi alla O(1)-luokan esimerkkialgoritmia voitaisiin käyttää esimerkkinä kaikissa muissakin luokissa (ylläolevan kolmannen pallukan nojalla). (Se, että kyseessä on yläraja, ei tarkoita sitä, että O(f)-luokkia käytettäisiin vain pahimman tapauksen analysointiin.) Funktioluokkia käytettäessä jäävät vakiokertoimet ja alempiasteiset termit huomiotta. Esimerkiksi T(n) = 101010 on O(1). Tällöin algoritmi, joka vie (jollakin tietyllä laitteistolla) aina 100 000 000 000 vuotta aikaa, näyttää paremmalta kuin algoritmi, jonka aikavaativuus on log n nanosekuntia (ja myös on parempi, kunhan n on tarpeeksi suuri...). Toisaalta suuruusluokka on yleensä helpompi analysoida kuin täsmällinen aikavaativuus. Esimerkkejä ja perusteluja: O(1) Alkion lisääminen linkitetyn listan alkuun on aikavaativuudeltaan O(1), koska siinä tarvitsee vain päivittää vakiomäärä linkkejä. O(log n) Haku tasapainoisesta binäärihakupuusta; binäärihaku järjestetystä taulukosta. Perusteluksi riittää vetoaminen "log n -sääntöön": O(1)-operaatiolla puolitetaan n. O(n) Haku järjestämättömästä taulukosta. Pahimmassa tapauksessa joudutaan käymään kaikki n alkiota läpi. (Tässä voi myös vedota "for-sääntöön"; tällöin oleellista on, että silmukan lopetusehto on muotoa c*n, missä c on vakio, ja että silmukassa suoritettava lause on aikavaativuudeltaan O(1). Siis ei for (i=0; i