WORST_CASE(?,O(n^1))

Solution:
---------

  "0" :: [] -(0)-> "nat"(15)
  "Cons" :: ["__ANY_TYPE__"(0) x "list"(2)] -(2)-> "list"(2)
  "Cons" :: ["__ANY_TYPE__"(0) x "list"(0)] -(0)-> "list"(0)
  "Nil" :: [] -(0)-> "list"(2)
  "Nil" :: [] -(0)-> "list"(15)
  "Nil" :: [] -(0)-> "list"(7)
  "S" :: ["nat"(0)] -(0)-> "nat"(15)
  "S" :: ["nat"(0)] -(0)-> "nat"(11)
  "S" :: ["nat"(0)] -(0)-> "nat"(10)
  "comp_f_g" :: ["list"(1) x "list"(1)] -(0)-> "list"(1)
  "comp_f_g#1" :: ["list"(1) x "list"(0) x "list"(0)] -(3)-> "list"(0)
  "main" :: [] -(16)-> "list"(0)
  "walk#1" :: ["list"(2)] -(8)-> "list"(1)
  "walk_xyz" :: [] -(0)-> "list"(1)
  "walk_xyz" :: [] -(0)-> "list"(7)
  "walk_xyz_3" :: ["nat"(0)] -(1)-> "list"(1)
  "walk_xyz_3" :: ["nat"(0)] -(0)-> "list"(0)


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




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



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

(STRATEGY
 INNERMOST)
(VAR
 "v4" "v3" "v2" "v1")
(DATATYPES
   "list" = µX.< "Nil", "walk_xyz", "Cons"("__ANY_TYPE__", X), "comp_f_g"(X, X), "walk_xyz_3"("nat") >
   "nat" = µX.< "S"(X), "0" >)
(SIGNATURES
   "walk#1" :: ["list"] --> "list"
   "comp_f_g#1" :: ["list" x "list" x "list"] --> "list"
   "main" :: [] --> "list")
(RULES
 "walk#1"("Nil"()) -> "walk_xyz"()
 "walk#1"("Cons"("v4","v3")) -> "comp_f_g"("walk#1"("v3"),"walk_xyz_3"("v4"))
 "comp_f_g#1"("comp_f_g"("v4","walk_xyz_3"("v3")),"walk_xyz_3"("v2"),"v1") -> "comp_f_g#1"("v4","walk_xyz_3"("v3"),"Cons"("v2","v1"))
 "comp_f_g#1"("walk_xyz"(),"walk_xyz_3"("v3"),"Cons"("v1","v2")) -> "Cons"("v3","Cons"("v1","v2"))
 "main"() -> "comp_f_g#1"("walk#1"("Cons"("S"("S"("0"())),"Cons"("S"("S"("S"("0"()))),"Nil"()))),"walk_xyz_3"("S"("0"())),"Nil"()))


WORST_CASE(?,O(n^1))