Wat is de tijdcomplexiteit van een bewerking die in een array van n elementen elk paar van twee verschillende elementen precies één keer vergelijkt (een dubbele lus die element i vergelijkt met alle elementen erna en i telkens één stap verder zet)?

Antwoord: C. O(n²)

Het aantal vergeleken paren is (n−1) + (n−2) + … + 1 = n(n−1)/2: 45 voor n = 10 en 499.500 voor n = 1000. De O-notatie kijkt alleen naar hoe het aantal groeit als n groot wordt, dus de factor 1/2 en de termen van lagere orde vallen weg en het resultaat is O(n²). Als n verdubbelt, wordt het aantal ongeveer vier keer zo groot. O(n) is de complexiteit van een bewerking die elk element één keer bekijkt, en O(n log n) die van algoritmen zoals mergesort, die de gegevens herhaaldelijk in tweeën delen.