[C++] Calcolo della relazione di ricorrenza

[Gianni91]

Originariamente inviato da ramy89
Niente, era R(n) = cn^4+R(n/2) se il for era scritto così:

for(int i=0;i<= x*x*x*x;i++) 
a+=i;

Ma se ho un risultato diverso vuol dire che va calcolato in un'altro modo..

Esempio:

int f(int x)
{
    if(x==0)
        return 1;
    else
    {
        int sum=0;
        for(int i=0;i<x;i++)
            sum+=i;
        return sum+f(x/2);
    }
}

Allora assegnando un costo costante al corpo del for che chiamo c, distingui due casi:
T(f(x))=1 se x=0
T(f(x))=xc+T(x/2) se x>1
E dalla relazione di ricorrenza sei in grado di calcolarti la complessità.

Ci sono quasi pienamento nel tuo ragionamento
Potresti esternare il tuo ragionamento magari mi é piu chiaro come ragionarci..