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) &\text{dla } n>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) &\text{dla } n>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?