Wyznacz f taką, że czas działania algorytmu znajduje się w Theta(f)

Witam,
pseudo kod funkcji rekurencyjnej, której dotyczy treść zadania:

INF(int poczatek, int koniec){
   suma:=0;
   for(i:=poczatek to i:=koniec)
       suma:=suma + t[i] + t[k];
  pom1:= poczatek + (koniec - poczatek +1)/3;
  pom2:= poczatek +2*(koniec - poczatek +1)/3;

return suma +2*INF(t, poczatek, pom1) + 6*INF(t,pom1,pom2)+INF(t,pom2,koniec);
}
 

a tu krótki kod programu wywołującego tą funkcję : http://pastebin.com/qcRn6NcB

Proszę o pomoc w rozwiązaniu zadania. Jak dla mnie ten algorytm nigdy się nie skończy. Może to nie jest błędem w zadaniu i istnieje jego logiczne rozwiązanie. Więc jeśli ktoś jest w stanie mi pomóc, byłbym wdzięczny za udzielenie wskazówek ;)

No przy takim zapisie to się na pewno nie skończy, to fakt. Ale przypuszczam że był tam jednak gdzieś na początku warunek żeby na przykład koniec z początkiem sie nie zeszły.

Właśnie nie. Dokładnie takie zadanie dostałem na kolosie, mogę przesłać zdj :p Może przekształćmy to zadanie i dodajmy warunek, że

poczatek != koniec

, albo koniec >1

. Chciałbym po prostu się dowiedzieć, jak rozwiązuje się takie zadania ;) Mam z tego ułożyć równanie rekurencyjne, coś w stylu:
T(1) = 1
T(3<sup>k</sup>) = ...
(tego równania też nie potrafię ułożyć... ).

Tak na prawdę to nie da się ułożyć tego równania, bo jak zdefiniujesz bazę równania rekurencyjnego jeśli rekurencja się nigdy nie kończy ?

No, ale przymykając na to oko, to powinno to wyglądać jakoś tak:

T(n) = T(n/3) + T(n/3) + T(n/3) = 3T(n/3). Wyglada jak coś liniowego, aczkolwiek nie mam pewności, trzeba by rozwiązać.