Confronto complessitàdi funzioni

[HaMyX]

Salve ragazzi. Volevo chiedere se potevate spiegare un metodo logico per confrontare 2 o + funzioni che hanno complessità diversa a seconda del valore in ingresso e dire se una è O-grande dell'altra e viceversa
esempio di un esercizio:
la funzione vale tot se n è tot (<--come leggere la tabella)
f(n)
( 3n^3+3 se n è primo
( n altrimenti

g(n)
( n^3 se l'ultima cifra di n è 0 o 5
( 4n^3 altrimenti

h(n)
( n^2 se n è divisore di 50
( n^3 altrimenti

C'è da dire se f è O(g(n)) e viceversa, e tutte le altre possibili combinazioni. Come si procede con un filo logico?

 

[Spider Murphy]

EDIT : Rileggendo meglio ho capito che a te serve la regola per esprimere il costo computazionale in notazione asintotica, la regola è questa

O(g(n))={f(n): ∃ c, n0 tali che
∀ n≥ n0
0 ≤ f(n) ≤ c g(n) }

Questo in poche parole significa che f è O(g(n)) se esiste una costante c che possa essere maggiorata da c g(n) per n abbastanza grandi.

In poche parole in base ad n il valore della funzione f(n) deve trovarsi sempre entro l'intervallo sopra definito 0 ≤ f(n) ≤ c g(n) estremi inclusi.

Dove g(n) è la funzione da confrontare.

Byez