Problemas de eficiencia

[lonrot]

Hola:

Me pondrian ayudar con esto:

En notacion O.
Si T(n) tiene la propiedad que T(0) es O(1), y T(n) <= T(n-1) + f(n) donde f(n) is una funcion que consume y regresa numeros naturals y que es O(n), entonces T(n) es O(n^2), pero como puedo probar esto por induccion??

Y el otro es:

Código:

(define (mod-exp1 m e n)
     (cond
         [(zero? e) 1]
         [else (modulo (* (mod-exp1 m (- e 1) n) m) n)]))

*El programa esta en scheme; es una funcion recursiva donde cond es igual a if en otros lenguajes y (* a b c) =(a*b*c)
Asumiendo que m E{0,...,n-1}, deja que T_1(e) sea el numero de multiplicaciones necesarias para calcular (mod-exp1 m e n) en una entrada legal. Da una formula explicita para T_1(e).

Gracias