Buongiorno a tutti!
Mi trovo in difficoltà su un esercizio in riferimento alla complessità di un algoritmo di tipo Las Vegas che campiona casualmente i vincoli e calcola il valore ottimo (LVIncrementalLP(V), programmazione lineare).
Devo dimostrare, applicando il metodo di sostituzione, che per un opportuna costante b,
$ T(n,d)<= T(n-1,d) + O(d)+ d/n(O(dn)+T(n-1,d-1)) $
è risolta da
$ T(n,d)<= bnd! $
Ovvero che la complessità è, per una costante b, lineare in n e fattoriale in d.
Non dev'essere difficile dimostrarlo, ma non saprei come fare!