Cześć,
Czy mógłby ktoś zerknąć na poniższy rysunek i powiedzieć jaka jest funkcja złożoności w najgorszym przypadku tego algorytmu? Załóżmy, że warunek Q to operacja elementarna.
Według mnie jest to F(n) = 2n-5
0
0
A nie powinno być 2N - 3
? (2N - K + 2
).
0
No jeśli warunek Q nigdy nie jest spełniony (czy też zawsze jest spełniony, ciężko stwierdzić która to jest tak krawędź, co idzie "w górę"), to algorytm się zapętla, i w efekcie nie masz skończonego czasu działania.