Najpierw wyznaczymy g(n) — liczbę wywołań rekurencyjnych, jaka zostanie wykonana przez funkcję F przy obliczaniu wartości wielomianu P(x) stopnia n − 1, gdzie n jest potęgą dwójki. Po przeprowadzeniu krótkiej analizy algorytmu możemy zauważyć, że jeśli n = 1, to funkcja F nie wykona żadnych dodatkowych wywołań rekurencyjnych, a więc
Natomiast dla n > 1 można zauważyć, że funkcja wykonuje dodatkowo dwa wywołania rekurencyjne dla tablic o połowę mniejszych, co oznacza, że
g(n) = 2g(n/2) + 1.
Uczeń może tutaj zauważyć podobieństwo do poprzedniego zadania. Jedyną różnicą jest to, że w powyższej rekurencji mamy warunek początkowy g(1) = 1. W zadaniu jednak należy znaleźć wzór ogólny dla g(n). Aby go wyprowadzić, warto wyznaczyć kilka początkowych wartości funkcji g(n), mianowicie mamy:
g(1) = 1
g(2) =2⋅g(1) + 1 = 3,
g(4) =2⋅g(2) + 1 = 7,
g(8) =2⋅g(4) + 1 = 15,
g(16) =2⋅g(8) + 1 = 31.
Stąd można wywnioskować, że g(n) = 2n – 1. Można to udowodnić za pomocą indukcji matematycznej.