[Algoritmi] Esercizio funzioni iterate e calcolo confronti

[devaroger89]

Ciao a tutti, ho un problema con questi due esercizi:

1)

Calcolare le funzioni iterate f ∗ (n) delle seguenti funzioni f (n):

$ f1 (n) = n − 1$
$f2 (n) =n/4$
$f3 (n) = log(n) $


2) Non so come procedere per rispondere a questa domandina:

Quanti confronti sono necessari per ordinare n^2 numeri?

Grazie in anticipo per l'aiuto/ consigli che mi darete!

[Howard_Wolowitz]

Innanzitutto direi che [tex]{f}_{1}(n)*(n) = n - n = 0[/tex], ovvero la sottrazione di 1 da un numero n iterata n volte equivale a 0.
Per la seconda se itero ottengo che, ad esempio, [tex]{f}_{2} * (2) = \frac{n}{16}[/tex], [tex]{f}_{2}*(3) = \frac{n}{64}[/tex] e quindi... [tex]{f}_{2}*(n) = \frac{n}{{4}^{n}}[/tex].
Per la terza penso si vada diretti verso la definizione di logaritmo iterato, ovvero logaritmo del logaritmo del logaritmo... insomma [tex]{f}_{3}*(n) = {log}^{(n)}n[/tex].

Per la seconda domanda, intuitivamente, arrivo a dire che se voglio ordinare un insieme di numeri attuerò una serie di confronti che mi porterà a confrontare l'n-esimo numero estratto dalla lista con, al più, gli n-1 numeri estratti in precedenza, questo per tutti i numeri estratti meno il primo; segue che il numero massimo di confronti necessari per una lista di n elementi è di [tex]\frac{n^2 - n}{2}[/tex], da qui il risultato per [tex]n^2[/tex].