W tym samym artykule wykazano również, że dla gramatyk jednoznacznych działanie uzupełniania wykonuje w i-tym zbiorze sytuacji O(i) kroków, co owocuje kwadratową złożonością algorytmu, oraz że klasa gramatyk, dla których algorytm Earleya działa w czasie liniowym, obejmuje gramatyki, dla których liczbę sytuacji w każdym zbiorze ogranicza z góry pewna stała. Do tej klasy należą prawie wszystkie gramatyki LR(k), oprócz niektórych gramatyk prawostronnie rekursywnych, więc także gramatyki większości języków programowania.
Algorytm Earleya działa szczególnie wydajnie z gramatykami o produkcjach lewostronnie rekursywnych. Jako przykład posłuży gramatyka S → Sa S → a
użyta do analizy ciągu aaa. Algorytm Earleya tworzy wówczas następujące sytuacje:
thumb|Drzewo rozbioru ciągu aaa w gramatyce lewostronnie rekursywnej
{| class="wikitable" |- style="background: #efefef;" ! Sytuacja Earleya !