[Algorytmy] Zlozonosc obliczeniowa algorytmu

[sinnervo]

Mam następujący algorytm:

Kod: Zaznacz cały

void Szukaj(Drzewo *drzewo, int x)
{
  if(drzewo != NULL) {
    if(x < drzewo->wartosc)
      Szukaj(drzewo->lewy, wartosc);
    else
      if(x > drzewo->wartosc)
	Szukaj(drzewo->prawy, x);
      else {
	/* x znalezione */
	printf("%d
", x);
	return;
      }
  } else {
    printf("Nie znalezione.
");
    return;
  }
}

Probuje oszacowac jego zlozonosc obliczeniowa. Aby to zrobic chce zapisac funkcje zlozonosci praktycznej.
\(\displaystyle{ T(n)=T(n/2)+\Theta(1)}\)

Czy do tego etapu zostalo to prawidlowo zapisane?

Nie wiem co zrobic dalej. Wiem, ze funkcja zlozonosci bedzie zawierac logarytm o podstawie 2. Nie rozumiem jednak dlaczego i byloby fajnie gdyby ktos zechcial to wyjasnic.

Pozdrawiam,