Rozwiąż rekurencje

Ktoś mógłby mi wytłumaczyć w jaki sposób rozwiązać taką rekurencję:

Robisz funkcję o nazwie T, która przyjmuje argument n i w ciele tej funkcji wrzucasz prawą stronę równania. Już w samym zapisie, który tutaj umieściłeś widać rekurencyjne wywołanie funkcji T z argumentem n/16.

a mógłbyś napisać jak to ma wyglądać?

EDIT:

T(n){
4T(n/16) + n^2;
}

dobrze? co dalej?

Zakładam double jako typ n.

double funkcja(double n) {
   if(n == <wartość>) return <wartość>;
   else {
      return 4*funkcja(n/16) + pow(n, 2);
   }
}

ok, a po co jest ten if(n == <wartość>)?
i skąd wiadomo ile wynosi "wartość"?

To właśnie powinien być jeden z warunków zadania. Jeżeli nie będzie tego warunku program będzie leciał z tą rekurencją w nieskończoność i nigdy się nie zatrzyma.

Rozumiem. W takim razie ile wynosi "wartość"?
I kiedy rekurencja się zatrzyma (skończy)?

Wklej cala tresc zadania, albo powiedz skad masz ten wzor i do czego on jest...

To jest całe zadanie z mojego sprawdzianu.
W poleceniu mam rozwiązać w/w rekurencję.

Dopoki nie masz warunku bazowego, niemozliwym jest napisanie innej rekurencji niz nieskonczona. :x

Anyway.. masz nieskonczona.

(define (T n)
  (+ (* 4
        (T (/ n 16)))
     (* n n)))

Tutaj nie trzeba chyba pisać algorytmu, tylko rozwiązać to np. metodą rekurencji uniwersalnej.

btanreb napisał(a):

Tutaj nie trzeba chyba pisać algorytmu, tylko rozwiązać to np. metodą rekurencji uniwersalnej.

A więc do dzieła: http://pl.wikipedia.org/wiki/Rekurencja_uniwersalna

Ktoś może sprawdzić czy to będzie 3 przypadek z tego linku: http://pl.wikipedia.org/wiki/Rekurencja_uniwersalna
Po podstawieniu wyszło mi n^33/64, ale "trochę" brakuje do n²...

btanreb napisał(a):

Ktoś może sprawdzić czy to będzie 3 przypadek z tego linku: http://pl.wikipedia.org/wiki/Rekurencja_uniwersalna
Po podstawieniu wyszło mi n^33/64, ale "trochę" brakuje do n²...

Trzeci przypadek. Mamy n^log_ba = n^log₁₆4 = n^1/2. Z kolei n² = Ω(n^{1/2 + ε}) oraz 4(n/16)² ≤ cn² np. dla c = 1/2, zatem T(n) = Θ(n²).

Ok, pomyliłem się w obliczaniu "c". Wszystko ok. Dzięki :)