Quel est le temps de fonctionnement? est-ce O (n)?

Question

Je pense que le temps d'exécution de cette solution est O (n). Mais je ne suis pas sur. Quelqu'un peut-il m'aider à le comprendre?

(define (poly x coeff) 
    (polyaux x (reverse coeff) 0)) 

;; the aux function 
(define (polyaux x coeff acc) 
    (if (null? coeff) 
     acc 
     (polyaux x (cdr coeff) (+ (* acc x) (car coeff))))) 

grâce

Answer 1

Si le n O (n) fait référence à la longueur de coeff, alors il doit être. À chaque étape, coeff obtient un élément plus court jusqu'à ce qu'il soit parti.