Ricorrenze e notazioni asintotiche

[AbraCadabra123]

(a)Siano f(n) e g(n) funzioni positive. Analizzare la seguente relazione 5f(n)+ g(n)/7 = Θ(f(n)+ g(n)). Dire se e vera o falsa, motivando e provando le proprie affermazioni.

(b) Risolvere la seguente relazione di ricorrenza: T(n)= T (n/5) + T (4n/5) + n con T (n)= O(1) per n ≤ 5.

Sperando che questo sia il luogo giusto, qualcuno mi potrebbe risolvere questi esercizi, ovviamente spiegandomi come procedere

[smartmouse]

Salve, anche io ho lo stesso esame con lo stesso prof!!

Avevo fatto lo stesso esercizio in questo modo:

Vogliamo verificare che:

$5f(n) + \frac{1}7g(n) = \Theta(f(n) + g(n))$

Dunque

$exists \ c,\ c' > 0 :\ c(f(n)+g(n)) \leq 5f(n) + \frac{1}7g(n) \leq c'(f(n)+g(n))$

Metto a sistema con $c$ e $c'$

${(5f(n) >= c(f(n))),(\frac{1}7g(n) >= c(g(n))):} => {(c <= 5),(c <= \frac{1}7):}$

${(5f(n) <= c'(f(n))),(\frac{1}7g(n) <= c'(g(n))):} => {(c' >= 5),(c' >= \frac{1}7):}$

Porta da qualche parte questo ragionamento?
Ho provato a seguire lo svolgimento della pagina precedente, ma non ho capito i vari $d_1$ e $d_2$...

[hamming_burst]

Ciao,

"smartmouse":Metto a sistema con $c$ e $c'$

${(5f(n) >= c(f(n))),(\frac{1}7g(n) >= c(g(n))):} => {(c <= 5),(c <= \frac{1}7):}$

${(5f(n) <= c'(f(n))),(\frac{1}7g(n) <= c'(g(n))):} => {(c' >= 5),(c' >= \frac{1}7):}$

Porta da qualche parte questo ragionamento?

questo modo di procedere lo ho già visto fare da qualche altro utente anni fa.
E' stato spiegato dal tuo docente questa schematizzazione?

cmq è simile a come ho mostrato nella pagina precedente, ma ha mio parere è sbagliato, perchè elimini l'informazione della somma tra funzioni.

[smartmouse]

No, è un procedimento mostrato da un mio amico.
Potresti spiegarmi meglio quello della pagina precedente?