[Algorytmy][Teoria złożoności] Wyszukiwanie binarne

[student353d]

Mam zadanie w którym muszę wykazać, że algorytm wyszukiwania binarnego (posortowanych danych). Wg wikipedii anglojęzycznej ów złożoność wynosi \(\displaystyle{ O(\log(n))}\). Posiadam pewien wzór, którym szczególnie łatwo wyliczyć liniową złożoność. Wygląda on następująco (wzór ogólny):
\(\displaystyle{ W(n) = \max(t(I))}\), gdzie \(\displaystyle{ t(I)}\) to liczba operacji wykonywanych przez algorytm. W pesymistycznym przypadku, dla algorytmu wyszukiwania binarnego, musimy sprawdzić wszystkie węzły. Nakazuje mi to więc sprawdzenie \(\displaystyle{ 2^{n+1}-1}\) węzłów. I jak niby z tego da się wyciągnąć logarytm? A może źle się zabieram za to?

[Mruczek]

Nakazuje mi to więc sprawdzenie \(\displaystyle{ 2^{n+1}-1}\) węzłów.

To jest jakaś kompletna bzdura.
Równanie rekurencyjne na binsearch to:
\(\displaystyle{ T \left( n \right) = T\left( \frac{n}{2}\right) + 1}\),
a ono daje ostatecznie czas \(\displaystyle{ O\left( \log n\right)}\).

[student353d]

Moje obliczenia (na rekurencję typu dziel i rządź):
\(\displaystyle{ T \left( n \right) =T \left( \frac{n}{2} \right) +1}\), gdzie \(\displaystyle{ a = 1, b = 2, c = 1, d \left( n \right) = 1}\)

\(\displaystyle{ T \left( n \right) = 1 + \sum_{i=0}^{k-1}2^{k-i}=1 + \sum_{i=0}^{k-1}\frac{2^{k}}{2^{i}}=1+2^{k}\sum_{i=0}^{k-1}\frac{1}{2^{i}}}\)

I co mam dalej robić, by otrzymać wspomniany już \(\displaystyle{ \log \left( n \right)}\)? Rozumiem również, że będzie to tożsame tylko z pesymistyczną złożonością algorytmu binsearch?