Przypomnijmy, że po wykonaniu pierwszej pętli n jest równe 2^k . Zauważmy też, że w pierwszym obrocie pętli „dopóki s < n wykonuj” instrukcja w wierszu (*) wykona się n/2 razy, w drugim obrocie pętli wykona się n/4 razy itd., w ostatnim obrocie wykona się jeden raz (dla s = 2^k–1 = n/2). Zatem instrukcja w wierszu (*) wykona się

1 + 2 + 4 + …+ n/4 + n/2 = n – 1

razy (zauważ, że liczby 1, 2, 4, … tworzą ciąg geometryczny). Oznacza to, że pierwsze z podanych czterech stwierdzeń jest prawdziwe, a drugie fałszywe (2n > n – 1 > n/2 dla n > 2).

Ponieważ wartość s jest w trakcie działania algorytmu większa od zera, a instrukcja zamiany z wiersza (**) wykonuje się tylko, gdy A[j] > A[j+s], instrukcja (**) nie zostanie wykonana ani razu dla ciągów uporządkowanych, czyli spełniających A[1] < A[2] < … < A[n]. Prawdziwe jest zatem stwierdzenie: „Możliwe jest dobranie takiej początkowej zawartości A[1..2^k ], że instrukcja zamiany z wiersza (**) nie wykona się ani razu”.

W celu ustalenia prawdziwości ostatniego z podanych zdań zauważmy, że liczba wykonań instrukcji z wiersza (**) jest nie większa od liczby wykonań instrukcji z wiersza (*). Ustaliliśmy wcześniej, że liczba wykonań (*) jest równa n – 1, zatem ostatnie z podanych w zadaniu zdań jest fałszywe: liczba wykonań (**) jest nie większa n – 1 < 2n² dla n > 0.