Prima di tutto ci tengo a ringraziare il Prof. Gobbino per le utilissime e chiarissime lezioni che gentilmente ha deciso di condividere con &quot;il popolo di internet&quot;, a cui appartengo; ma vengo subito al punto.

Studio ing. informatica, e in un corso di algoritmi che sto frequentando mi è sorto un problema di carattere matematico, sulle successioni per ricorrenza. Queste sono tirate in ballo quando si cerca la complessità (efficenza) asintotica di un algoritmo, definita come &quot;quanto impiega un algoritmo, su un dato input di lunghezza n, a portarsi a termine&quot;. 

In breve è una funzione T : N --&gt; N debolmente crescente, in cui l'immagine è da intendersi come numero di passi compiuti dall'algoritmo, dato l'input. Di questa funzione si è interessati a capire il comportamento asintotico per n--&gt;+inf, ovvero a dare una stima di T tramite O-grande, Theta (asintoticità a meno di una costante davanti) etc.  Solitamente T è data come soluzione di un eq. alle ricorrenze, esempio:

T(n) = T(n/3) + Theta(log(n))    

Come si comporta T all'infinito? Essendo debolmente crescente ammette limite e si vede che è +inf, ma non serve a molto nell'analisi senza capire in che modo questa ci tenda.

Mi chiedevo come approcciare in modo rigoroso un problema di questo tipo. Malgrado i miei sforzi, non sono riuscito a venirne a capo. Chiedo quindi aiuto a lei, o a chiunque sappia aiutarmi.

P.S. Nei corsi di informatica equazioni come queste vengono risolte affidandosi al cosiddetto &quot;Master Theorem&quot;, applicato &quot;bovinamente&quot; e senza capirne il senso.