Należy zauważyć, że w każdym wywołaniu funkcji F(n) argument jest zmniejszany dwukrotnie. Pytanie o złożoność można zamienić na pytanie: Ile razy należy dzielić n na pół, aby uzyskać n = 1? Dla n = 8 = 2³ kolejne wywołania funkcji to F(4), F(2), F(1), czyli dzielenie występuje 3 razy. Dla n = 16 = 2⁴ kolejne wywołania to F(8), F(4), F(2), F(1), czyli dzielenie występuje 4 razy. Dla n = 2^k takie dzielenie będzie występowało k razy, zatem złożoność algorytmu jest logarytmiczna.