;;; Q$8$

;;;;

;;; What is the worst$-$case complexity of erl in terms of the length of xs$?$

;;; Hint: count the number of conses $($erl xs n$)$ performs when

;;; n $=($len xs$)-1.$ Uncomment the right answer.

; $($defconst "constant"$)$

; $($defconst "linear"$)$

; $($defconst "quadratic"$)$

; $($defconst "cubic"$)$

; $($defconst "exponential"$)$

;;; Provide an explanation of your answer by replacing the XXX in the

;;; string below with your answer.

$($defconst $"$XXX$")$

;;; Q$9$

;;;;

;;; Define a linear time version of rl$.$ Feel free to define any

;;; helper functions you may need. The only functions you can use are the ones

;;; in the ACL$2$s reference $($click on "Lecture Notes" from the class

;;; Webpage$).$

$($definec rl$-$fast $($xs :tl n :nat$)$ :tl

XXX$)$