Witam
Mam proste zadanie (ze słynnej książki: "Wprowadzenie do algorytmów" ze
strony 87. nr 4.3-2) o treści:

Pokaż, że rozwiązanie równania T(n) = T(sufit(n/2)) + 1 jest O(lg(n)).

Postępowałem wg metody podstawiania podanej 4 strony wcześniej:
Przyjąłem tezę (do udowodnienia), że ma być T(n) <= clg(n) dla c>0
które zachodzi dla wszytkich m < n, a w szczególności dla m=sufit(n/2).
Tzn.:
T(sufit(n/2)) <= clg(sufit(n/2))

Teraz podstawiam to do równiania rekurencyjnego i mam:
T(n) <= clg(sufit(n/2)) + 1
= clg(n/2 + n mod 2) + 1

Tego już chyba nie trzeba redukować jednak należy sprawdzić, czy jest to
<= clg(n)

Biorę n = 17 i mam:
clg(n/2 + n mod 2) + 1 = clg(8 + 1) + 1 = 4,1699
clg(n) = clg(17) = 4,0875

Czy to znaczy, że obaliłem tezę zdania? I że ten algorytm wcale nie jest
O(lg(n))?!?

dzięki i pozdro
Szyk Cech

ps.: lg to logarytm o podstawie 2

do góry