WORST_CASE(?,O(n^1))

Solution:
---------

  "Cons" :: ["__ANY_TYPE__"(0) x "list"(0)] -(0)-> "list"(15)
  "Cons" :: ["__ANY_TYPE__"(0) x "list"(0)] -(0)-> "list"(12)
  "Leaf" :: ["__ANY_TYPE__"(15)] -(15)-> "tree"(15)
  "Nil" :: [] -(0)-> "list"(15)
  "Node" :: ["tree"(15) x "tree"(15)] -(15)-> "tree"(15)
  "comp_f_g" :: ["list"(5) x "list"(5)] -(5)-> "list"(5)
  "comp_f_g#1" :: ["list"(5) x "list"(5) x "list"(12)] -(1)-> "list"(12)
  "cons_x" :: ["__ANY_TYPE__"(0)] -(0)-> "list"(5)
  "cons_x" :: ["__ANY_TYPE__"(0)] -(0)-> "list"(7)
  "main" :: ["tree"(15)] -(9)-> "list"(5)
  "walk#1" :: ["tree"(15)] -(0)-> "list"(5)


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

  "Cons" :: ["__ANY_TYPE__"_cf(0) x "list"_cf(0)] -(0)-> "list"_cf(0)
  "Leaf" :: ["__ANY_TYPE__"_cf(0)] -(0)-> "tree"_cf(0)
  "Node" :: ["tree"_cf(0) x "tree"_cf(0)] -(0)-> "tree"_cf(0)
  "comp_f_g" :: ["list"_cf(0) x "list"_cf(0)] -(0)-> "list"_cf(0)
  "comp_f_g#1" :: ["list"_cf(0) x "list"_cf(0) x "list"_cf(0)] -(0)-> "list"_cf(0)
  "cons_x" :: ["__ANY_TYPE__"_cf(0)] -(0)-> "list"_cf(0)
  "walk#1" :: ["tree"_cf(0)] -(0)-> "list"_cf(0)


Base Constructors:
------------------
  "\"Cons\"_list" :: ["__ANY_TYPE__"(0) x "list"(0)] -(0)-> "list"(1)
  "\"Leaf\"_tree" :: ["__ANY_TYPE__"(1)] -(1)-> "tree"(1)
  "\"Nil\"_list" :: [] -(0)-> "list"(1)
  "\"Node\"_tree" :: ["tree"(1) x "tree"(1)] -(1)-> "tree"(1)
  "\"comp_f_g\"_list" :: ["list"(0) x "list"(0)] -(1)-> "list"(1)
  "\"cons_x\"_list" :: ["__ANY_TYPE__"(0)] -(0)-> "list"(1)



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

(STRATEGY
 INNERMOST)
(VAR
 "v2" "v5" "v3" "v4" "v1" "v7" "v9")
(DATATYPES
   "list" = µX.< "cons_x"("__ANY_TYPE__"), "comp_f_g"(X, X), "Cons"("__ANY_TYPE__", X), "Nil" >
   "tree" = µX.< "Leaf"("__ANY_TYPE__"), "Node"(X, X) >)
(SIGNATURES
   "walk#1" :: ["tree"] --> "list"
   "comp_f_g#1" :: ["list" x "list" x "list"] --> "list"
   "main" :: ["tree"] --> "list")
(RULES
 "walk#1"("Leaf"("v2")) -> "cons_x"("v2")
 "walk#1"("Node"("v5","v3")) -> "comp_f_g"("walk#1"("v5"),"walk#1"("v3"))
 "comp_f_g#1"("comp_f_g"("v4","v5"),"comp_f_g"("v2","v3"),"v1") -> "comp_f_g#1"("v4","v5","comp_f_g#1"("v2","v3","v1"))
 "comp_f_g#1"("comp_f_g"("v7","v9"),"cons_x"("v2"),"v4") -> "comp_f_g#1"("v7","v9","Cons"("v2","v4"))
 "comp_f_g#1"("cons_x"("v2"),"comp_f_g"("v5","v7"),"v3") -> "Cons"("v2","comp_f_g#1"("v5","v7","v3"))
 "comp_f_g#1"("cons_x"("v5"),"cons_x"("v2"),"v4") -> "Cons"("v5","Cons"("v2","v4"))
 "main"("Leaf"("v4")) -> "Cons"("v4","Nil"())
 "main"("Node"("v9","v5")) -> "comp_f_g#1"("walk#1"("v9"),"walk#1"("v5"),"Nil"()))


WORST_CASE(?,O(n^1))