Najdłuższy palindrom - złożoność

Hej,
Mam takie zadanko:
Poniższy algorytm dla zadanego słowa w = w₁w₂...w_n znajduje najdłuższym palindrom będący jego podsłowem (np. dla słowa skok algorytm zwróci kok)
Maxpali(w)

i := 1
j := n
while (i<j) and (wi =wj) do 
	i := i +1
	j := j -1
if i = j
	then return w
else 
	u := Maxpali(w1…wn-1)
	v := Maxpali(w2…wn)
if |u| > |v|
	then return u
else
	return v

Pokaż, że złożoność obliczeniowa tego algorytmu jest Ω(2)ⁿ

Czy w zadaniu nie powinno być pytanie dla notacji O?
Ponieważ: notacja omega - asymptotyczna granica dolna. W najlepszym przypadku słowo jest palindromem i złożoność algorytmu będzie liniowa.

Załóżmy, że jest to dla notacji O.
$\left{\begin{array}{l} f(1) = 1\f(n) = f(n-1) + f(n-1) &\text{dla } n>0\end{array}$
//bo 2 wywołania rekurencyjne dla zmniejszonych o 1 łańcuchów