Odświeżam nieco twierdzenie mistrza i próbuję ustalić czas działania algorytmu, który rozwiązuje problem rozmiarun rekurencyjnie rozwiązując 2 problemy o rozmiarachn-1 i łącz rozwiązania w stałym czasie.
Więc formuła jest:
T(N) = 2T(N - 1) + O(1)
Ale nie jestem pewien, jak sformułować warunek twierdzenia głównego.
To znaczy nie mamyT(N/b) więc jestb wzoru twierdzenia głównego w tym przypadkub=N/(N-1)?
Jeśli tak, to oczywiściea > b^k odk=0 i jestO(N^z) gdziez=log2 z podstawą(N/N-1) jak mogę to zrozumieć? Zakładając, że do tej pory mam rację?