T (n) = t (n - sqrt (n))

Question

Qualcuno sa come risolvere questa ricorrenza?

Il maestro teorema non funziona qui.

Answer 1

Sembra ovvio in O (1) da allora

T(n) = T(n - sqrt(n)) = T(m) with 0 < m < n

Per induzione, ottieni t (n) = t (epsilon) con epsilon vicino a 0.

La domanda rende più sens se era t (n) = t (n - sqrt (n)) + m

Answer 2

Hai ragione sul fatto che il teorema di Masters non si applica qui. Se guarderai più da vicino, vedrai che il costo della ricorsione è zero (non esiste un elemento gratuito sul lato destro: T(n) = T(m) + f(n).

Ciò significa che non ti costa assolutamente nulla eseguire la tua ricorsione (nemmeno 1 operazione). Quindi finché il tuo n diminuisce oltre le iterazioni (e lo fa perché n > n - sqrt(n)) La tua ricorsione è in realtà gratuita.

Quindi la risposta è O(1). PS Non è possibile avere questo nella vita reale perché farai almeno O (1) come costo della ricorsione.