Hej,
Mam takie zadanko:
Poniższy algorytm dla zadanego słowa w = w1w2...wn 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)n

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) &amp;\text{dla } n&gt;0\end{array}
//bo 2 wywołania rekurencyjne dla zmniejszonych o 1 łańcuchów

\left{\begin{array}{l} f(1) = 1\f(n) = 2f(n-1) &amp;\text{dla } n&gt;0\end{array}

f(n)=2\cdot2\cdot2\cdot...\ \cdot1,
f(n)=2^{n - 1} \cdot1,

Otrzymana f(n)=2<sup>{n - 1} \cdot1, jest tego samego rzędu co O(2)</sup>{n}, -> Czy myślicie, że to jest wystarczający dowód?