WORST_CASE(?,O(n^1))

Solution:
---------

  "0" :: [] -(0)-> "nat"(9)
  "0" :: [] -(0)-> "nat"(0)
  "Cons" :: ["__ANY_TYPE__"(11) x "list"(11)] -(11)-> "list"(11)
  "Nil" :: [] -(0)-> "list"(11)
  "S" :: ["nat"(9)] -(9)-> "nat"(9)
  "S" :: ["nat"(0)] -(0)-> "nat"(0)
  "fold#3" :: ["list"(11)] -(4)-> "nat"(0)
  "main" :: ["list"(12)] -(5)-> "nat"(0)
  "plus#2" :: ["nat"(9) x "nat"(0)] -(1)-> "nat"(0)


Cost Free Signatures:
---------------------




Base Constructors:
------------------
  "\"0\"_nat" :: [] -(0)-> "nat"(1)
  "\"Cons\"_list" :: ["__ANY_TYPE__"(1) x "list"(1)] -(1)-> "list"(1)
  "\"Nil\"_list" :: [] -(0)-> "list"(1)
  "\"S\"_nat" :: ["nat"(1)] -(1)-> "nat"(1)



Parsed Typed Term Rewrite System:
---------------------------------

(STRATEGY
 INNERMOST)
(VAR
 "v12" "v4" "v2" "v1")
(DATATYPES
   "list" = µX.< "Nil", "Cons"("__ANY_TYPE__", X) >
   "nat" = µX.< "0", "S"(X) >)
(SIGNATURES
   "plus#2" :: ["nat" x "nat"] --> "nat"
   "fold#3" :: ["list"] --> "nat"
   "main" :: ["list"] --> "nat")
(RULES
 "plus#2"("0"(),"v12") -> "v12"
 "plus#2"("S"("v4"),"v2") -> "S"("plus#2"("v4","v2"))
 "fold#3"("Nil"()) -> "0"()
 "fold#3"("Cons"("v4","v2")) -> "plus#2"("v4","fold#3"("v2"))
 "main"("v1") -> "fold#3"("v1"))


WORST_CASE(?,O(n^1))