BEST_CASE(Omega(n^2),?)

Solution:
---------

  "0" :: [] -(0)-> "nat"(0, 0)
  "0" :: [] -(0)-> "nat"(1, 0)
  "Cons" :: ["__ANY_TYPE__"(0, 0) x "list"(0, 0)] -(0)-> "list"(0, 0)
  "Cons" :: ["__ANY_TYPE__"(0, 0) x "list"(0, 2)] -(1)-> "list"(0, 1)
  "Cons" :: ["__ANY_TYPE__"(0, 0) x "list"(2, 6)] -(4)-> "list"(1, 3)
  "False" :: [] -(0)-> "bool"(15, 5)
  "False" :: [] -(0)-> "bool"(15, 15)
  "False" :: [] -(0)-> "bool"(13, 8)
  "False" :: [] -(0)-> "bool"(0, 4)
  "False" :: [] -(0)-> "bool"(3, 3)
  "False" :: [] -(0)-> "bool"(3, 4)
  "Nil" :: [] -(0)-> "list"(0, 0)
  "Nil" :: [] -(0)-> "list"(0, 1)
  "Nil" :: [] -(0)-> "list"(1, 3)
  "Pair" :: ["__ANY_TYPE__"(0, 0) x "__ANY_TYPE__"(0, 0)] -(0)-> "pair"(0, 0)
  "Pair" :: ["__ANY_TYPE__"(1, 0) x "__ANY_TYPE__"(0, 0)] -(1)-> "pair"(1, 0)
  "S" :: ["nat"(0, 0)] -(0)-> "nat"(0, 0)
  "S" :: ["nat"(1, 0)] -(1)-> "nat"(1, 0)
  "Triple" :: ["__ANY_TYPE__"(0, 0) x "__ANY_TYPE__"(0, 0) x "__ANY_TYPE__"(0, 0)] -(0)-> "triple"(0, 0)
  "True" :: [] -(0)-> "bool"(15, 5)
  "True" :: [] -(0)-> "bool"(15, 15)
  "True" :: [] -(0)-> "bool"(13, 8)
  "True" :: [] -(0)-> "bool"(0, 5)
  "True" :: [] -(0)-> "bool"(3, 5)
  "append#2" :: ["list"(0, 0) x "list"(0, 0)] -(1)-> "list"(0, 0)
  "bot[1]" :: [] -(0)-> "nat"(0, 0)
  "bot[2]" :: [] -(0)-> "list"(0, 0)
  "cid_map_1" :: ["nat"(0, 0)] -(0)-> "bool"(0, 0)
  "cond_average_grade'_student_id_course_ids_table" :: ["pair"(0, 0)] -(2)-> "nat"(0, 0)
  "cond_average_grade'_student_id_course_ids_table_1" :: ["triple"(0, 0)] -(1)-> "nat"(0, 0)
  "cond_div_mod_n_m" :: ["pair"(1, 0) x "nat"(0, 0)] -(0)-> "triple"(0, 0)
  "cond_div_mod_n_m_2" :: ["triple"(0, 0) x "nat"(0, 0)] -(1)-> "triple"(0, 0)
  "cond_quicksort_gt_acc_l_1" :: ["triple"(0, 0) x "pair"(0, 0) x "nat"(0, 0)] -(2)-> "pair"(0, 0)
  "cond_quicksort_gt_acc_l_2" :: ["pair"(0, 0) x "pair"(0, 0) x "nat"(0, 0) x "list"(0, 0)] -(1)-> "pair"(0, 0)
  "cond_quicksort_gt_acc_l_3" :: ["pair"(0, 0) x "nat"(0, 0) x "list"(0, 0)] -(1)-> "pair"(0, 0)
  "cond_sort_students_efficient_student_ids_course_ids" :: ["pair"(0, 0)] -(1)-> "list"(0, 0)
  "div_mod#2" :: ["nat"(1, 0) x "nat"(0, 0)] -(2)-> "triple"(0, 0)
  "eqNat#2" :: ["nat"(0, 0) x "nat"(0, 0)] -(1)-> "bool"(5, 5)
  "f" :: ["nat"(0, 0)] -(0)-> "pair"(0, 0)
  "f_1" :: ["nat"(0, 0) x "list"(0, 0)] -(0)-> "pair"(0, 0)
  "find#2" :: ["bool"(0, 0) x "list"(0, 0)] -(1)-> "list"(0, 0)
  "find2#2" :: ["bool"(0, 0) x "list"(0, 0)] -(1)-> "nat"(0, 0)
  "foldl2#3" :: ["pair"(0, 0) x "pair"(0, 0) x "list"(0, 0)] -(1)-> "pair"(0, 0)
  "geqNat#2" :: ["nat"(0, 0) x "nat"(0, 0)] -(1)-> "bool"(4, 6)
  "greater_eq'_course_ids" :: ["list"(0, 0)] -(0)-> "pair"(0, 0)
  "greater_eq'_course_ids_sid1" :: ["list"(0, 0) x "nat"(0, 0)] -(0)-> "pair"(0, 0)
  "ite2#3" :: ["bool"(15, 15) x "list"(0, 0) x "list"(0, 0)] -(1)-> "list"(0, 0)
  "ite3#3" :: ["bool"(15, 5) x "nat"(0, 0)] -(1)-> "nat"(0, 0)
  "ite_b#2" :: ["bool"(13, 8) x "triple"(0, 0) x "triple"(0, 0)] -(1)-> "triple"(0, 0)
  "lookup_sid_cid_table_1" :: ["nat"(0, 0)] -(0)-> "bool"(0, 0)
  "main" :: ["list"(0, 0) x "list"(0, 1)] -(1)-> "list"(0, 0)
  "map#2" :: ["pair"(0, 0) x "list"(0, 0)] -(1)-> "list"(0, 0)
  "minus'#2" :: ["nat"(1, 0) x "nat"(0, 0)] -(1)-> "nat"(1, 0)
  "mk_table#2" :: ["list"(0, 0) x "list"(0, 0)] -(1)-> "list"(0, 0)
  "partition#3" :: ["pair"(0, 0) x "triple"(0, 0) x "list"(1, 3)] -(1)-> "triple"(0, 0)
  "plus#2" :: ["nat"(0, 0) x "nat"(0, 0)] -(1)-> "nat"(0, 0)
  "quicksort#3" :: ["pair"(0, 0) x "list"(0, 0) x "list"(0, 1)] -(1)-> "pair"(0, 0)


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




Base Constructors:
------------------
  "\"0\"_nat" :: [] -(0)-> "nat"(1, 0)
  "\"0\"_nat" :: [] -(0)-> "nat"(0, 1)
  "\"Cons\"_list" :: ["__ANY_TYPE__"(0, 0) x "list"(2, 0)] -(1)-> "list"(1, 0)
  "\"Cons\"_list" :: ["__ANY_TYPE__"(0, 0) x "list"(0, 2)] -(1)-> "list"(0, 1)
  "\"False\"_bool" :: [] -(0)-> "bool"(1, 0)
  "\"False\"_bool" :: [] -(0)-> "bool"(0, 1)
  "\"Nil\"_list" :: [] -(0)-> "list"(1, 0)
  "\"Nil\"_list" :: [] -(0)-> "list"(0, 1)
  "\"Pair\"_pair" :: ["__ANY_TYPE__"(1, 0) x "__ANY_TYPE__"(0, 0)] -(1)-> "pair"(1, 0)
  "\"Pair\"_pair" :: ["__ANY_TYPE__"(0, 9) x "__ANY_TYPE__"(0, 0)] -(1)-> "pair"(0, 1)
  "\"S\"_nat" :: ["nat"(1, 0)] -(1)-> "nat"(1, 0)
  "\"S\"_nat" :: ["nat"(0, 8)] -(1)-> "nat"(0, 1)
  "\"Triple\"_triple" :: ["__ANY_TYPE__"(2, 0) x "__ANY_TYPE__"(0, 0) x "__ANY_TYPE__"(0, 0)] -(1)-> "triple"(1, 0)
  "\"Triple\"_triple" :: ["__ANY_TYPE__"(0, 8) x "__ANY_TYPE__"(0, 0) x "__ANY_TYPE__"(0, 0)] -(1)-> "triple"(0, 1)
  "\"True\"_bool" :: [] -(0)-> "bool"(1, 0)
  "\"True\"_bool" :: [] -(0)-> "bool"(0, 1)
  "\"bot[1]\"_nat" :: [] -(0)-> "nat"(1, 0)
  "\"bot[1]\"_nat" :: [] -(0)-> "nat"(0, 1)
  "\"bot[2]\"_list" :: [] -(0)-> "list"(1, 0)
  "\"bot[2]\"_list" :: [] -(0)-> "list"(0, 1)
  "\"cid_map_1\"_bool" :: ["nat"(0)] -(1)-> "bool"(1, 0)
  "\"cid_map_1\"_bool" :: ["nat"(0)] -(1)-> "bool"(0, 1)
  "\"f\"_pair" :: ["nat"(8, 0)] -(1)-> "pair"(1, 0)
  "\"f\"_pair" :: ["nat"(2, 1)] -(1)-> "pair"(0, 1)
  "\"f_1\"_pair" :: ["nat"(0) x "list"(0)] -(1)-> "pair"(1, 0)
  "\"f_1\"_pair" :: ["nat"(0) x "list"(0)] -(1)-> "pair"(0, 1)
  "\"greater_eq'_course_ids\"_pair" :: ["list"(0)] -(1)-> "pair"(1, 0)
  "\"greater_eq'_course_ids\"_pair" :: ["list"(0)] -(1)-> "pair"(0, 1)
  "\"greater_eq'_course_ids_sid1\"_pair" :: ["list"(0) x "nat"(0)] -(1)-> "pair"(1, 0)
  "\"greater_eq'_course_ids_sid1\"_pair" :: ["list"(0) x "nat"(0)] -(1)-> "pair"(0, 1)
  "\"lookup_sid_cid_table_1\"_bool" :: ["nat"(0)] -(1)-> "bool"(1, 0)
  "\"lookup_sid_cid_table_1\"_bool" :: ["nat"(0)] -(1)-> "bool"(0, 1)



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

(STRATEGY
 INNERMOST)
(VAR
 "v24" "v25" "v2" "v6" "v4" "v26" "v27" "v1" "v3" "v5" "v9" "v11"
 "v8" "v14" "v69" "v21" "v13" "v12" "v29" "v48" "v72" "v80" "v32"
 "v36" "v16" "v20")
(DATATYPES
   "bool" = < "lookup_sid_cid_table_1"("nat"), "cid_map_1"("nat"), "True", "False" >
   "list" = µX.< "Nil", "Cons"("__ANY_TYPE__", X), "bot[2]" >
   "nat" = µX.< "S"(X), "bot[1]", "0" >
   "pair" = < "Pair"("__ANY_TYPE__", "__ANY_TYPE__"), "f"("nat"), "f_1"("nat", "list"), "greater_eq'_course_ids"("list"), "greater_eq'_course_ids_sid1"("list", "nat") >
   "triple" = < "Triple"("__ANY_TYPE__", "__ANY_TYPE__", "__ANY_TYPE__") >)
(SIGNATURES
   "cond_sort_students_efficient_student_ids_course_ids" :: ["pair"] --> "list"
   "mk_table#2" :: ["list" x "list"] --> "list"
   "cond_average_grade'_student_id_course_ids_table_1" :: ["triple"] --> "nat"
   "cond_average_grade'_student_id_course_ids_table" :: ["pair"] --> "nat"
   "foldl2#3" :: ["pair" x "pair" x "list"] --> "pair"
   "find2#2" :: ["bool" x "list"] --> "nat"
   "find#2" :: ["bool" x "list"] --> "list"
   "map#2" :: ["pair" x "list"] --> "list"
   "cond_quicksort_gt_acc_l_3" :: ["pair" x "nat" x "list"] --> "pair"
   "cond_quicksort_gt_acc_l_2" :: ["pair" x "pair" x "nat" x "list"] --> "pair"
   "cond_quicksort_gt_acc_l_1" :: ["triple" x "pair" x "nat"] --> "pair"
   "quicksort#3" :: ["pair" x "list" x "list"] --> "pair"
   "partition#3" :: ["pair" x "triple" x "list"] --> "triple"
   "append#2" :: ["list" x "list"] --> "list"
   "ite3#3" :: ["bool" x "nat"] --> "nat"
   "ite2#3" :: ["bool" x "list" x "list"] --> "list"
   "ite_b#2" :: ["bool" x "triple" x "triple"] --> "triple"
   "cond_div_mod_n_m_2" :: ["triple" x "nat"] --> "triple"
   "cond_div_mod_n_m" :: ["pair" x "nat"] --> "triple"
   "div_mod#2" :: ["nat" x "nat"] --> "triple"
   "minus'#2" :: ["nat" x "nat"] --> "nat"
   "plus#2" :: ["nat" x "nat"] --> "nat"
   "geqNat#2" :: ["nat" x "nat"] --> "bool"
   "eqNat#2" :: ["nat" x "nat"] --> "bool"
   "main" :: ["list" x "list"] --> "list")
(RULES
 "cond_sort_students_efficient_student_ids_course_ids"("Pair"("v24","v25")) -> "v24"
 "mk_table#2"("Nil"(),"v2") -> "Nil"()
 "mk_table#2"("Cons"("v6","v4"),"v2") -> "Cons"("Pair"("v6","map#2"("f"("v6"),"v2")),"mk_table#2"("v4","v2"))
 "cond_average_grade'_student_id_course_ids_table_1"("Triple"("v25","v26","v27")) -> "v25"
 "cond_average_grade'_student_id_course_ids_table"("Pair"("v2","v1")) -> "cond_average_grade'_student_id_course_ids_table_1"("div_mod#2"("v1","v2"))
 "foldl2#3"("f_1"("v3","v2"),"v1","Nil"()) -> "v1"
 "foldl2#3"("f_1"("v6","v5"),"Pair"("v4","v3"),"Cons"("v2","v1")) -> "foldl2#3"("f_1"("v6","v5"),"Pair"("S"("v4"),"plus#2"("v3","find2#2"("lookup_sid_cid_table_1"("v2"),"find#2"("cid_map_1"("v6"),"v5")))),"v1")
 "find2#2"("lookup_sid_cid_table_1"("v1"),"Nil"()) -> "bot[1]"()
 "find2#2"("lookup_sid_cid_table_1"("v3"),"Cons"("Pair"("v2","S"("0"())),"v1")) -> "ite3#3"("eqNat#2"("v2","v3"),"find2#2"("lookup_sid_cid_table_1"("v3"),"v1"))
 "find#2"("cid_map_1"("v1"),"Nil"()) -> "bot[2]"()
 "find#2"("cid_map_1"("v4"),"Cons"("Pair"("v2","v9"),"v5")) -> "ite2#3"("eqNat#2"("v4","v2"),"v9","find#2"("cid_map_1"("v4"),"v5"))
 "map#2"("f"("v1"),"Nil"()) -> "Nil"()
 "map#2"("f"("v4"),"Cons"("v2","v11")) -> "Cons"("Pair"("v2","S"("0"())),"map#2"("f"("v4"),"v11"))
 "cond_quicksort_gt_acc_l_3"("Pair"("v4","v3"),"v2","v1") -> "Pair"("append#2"("Cons"("v2","v1"),"v4"),"v3")
 "cond_quicksort_gt_acc_l_2"("Pair"("v5","v4"),"greater_eq'_course_ids"("v3"),"v2","v1") -> "cond_quicksort_gt_acc_l_3"("quicksort#3"("greater_eq'_course_ids"("v3"),"v4","v1"),"v2","v5")
 "cond_quicksort_gt_acc_l_1"("Triple"("v5","v4","v3"),"greater_eq'_course_ids"("v2"),"v1") -> "cond_quicksort_gt_acc_l_2"("quicksort#3"("greater_eq'_course_ids"("v2"),"v3","v5"),"greater_eq'_course_ids"("v2"),"v1","v4")
 "quicksort#3"("greater_eq'_course_ids"("v4"),"v2","Nil"()) -> "Pair"("Nil"(),"v2")
 "quicksort#3"("greater_eq'_course_ids"("v8"),"v14","Cons"("v4","v6")) -> "cond_quicksort_gt_acc_l_1"("partition#3"("greater_eq'_course_ids_sid1"("v8","v4"),"Triple"("Nil"(),"Nil"(),"v14"),"v6"),"greater_eq'_course_ids"("v8"),"v4")
 "partition#3"("greater_eq'_course_ids_sid1"("v3","v2"),"v1","Nil"()) -> "v1"
 "partition#3"("greater_eq'_course_ids_sid1"("v8","v69"),"Triple"("v21","v13","v4"),"Cons"("v12","v29")) -> "ite_b#2"("geqNat#2"("cond_average_grade'_student_id_course_ids_table"("foldl2#3"("f_1"("v69","v4"),"Pair"("0"(),"0"()),"v8")),"cond_average_grade'_student_id_course_ids_table"("foldl2#3"("f_1"("v12","v4"),"Pair"("0"(),"0"()),"v8"))),"partition#3"("greater_eq'_course_ids_sid1"("v8","v69"),"Triple"("v21","Cons"("v12","v13"),"v4"),"v29"),"partition#3"("greater_eq'_course_ids_sid1"("v8","v69"),"Triple"("Cons"("v12","v21"),"v13","v4"),"v29"))
 "append#2"("Nil"(),"v48") -> "v48"
 "append#2"("Cons"("v6","v4"),"v2") -> "Cons"("v6","append#2"("v4","v2"))
 "ite3#3"("True"(),"v1") -> "S"("0"())
 "ite3#3"("False"(),"v1") -> "v1"
 "ite2#3"("True"(),"v72","v80") -> "v72"
 "ite2#3"("False"(),"v72","v80") -> "v80"
 "ite_b#2"("True"(),"v32","v36") -> "v32"
 "ite_b#2"("False"(),"v32","v36") -> "v36"
 "cond_div_mod_n_m_2"("Triple"("v4","v3","v2"),"v1") -> "Triple"("plus#2"("S"("0"()),"v4"),"v3","v1")
 "cond_div_mod_n_m"("Pair"("0"(),"v2"),"v1") -> "Triple"("0"(),"v1","v2")
 "cond_div_mod_n_m"("Pair"("S"("v3"),"v2"),"v1") -> "cond_div_mod_n_m_2"("div_mod#2"("S"("v3"),"v2"),"v2")
 "div_mod#2"("v8","v4") -> "cond_div_mod_n_m"("Pair"("minus'#2"("v8","v4"),"v4"),"v8")
 "minus'#2"("0"(),"v32") -> "0"()
 "minus'#2"("S"("v36"),"0"()) -> "S"("v36")
 "minus'#2"("S"("v4"),"S"("v2")) -> "minus'#2"("v4","v2")
 "plus#2"("v16","0"()) -> "v16"
 "plus#2"("v4","S"("v2")) -> "S"("plus#2"("v4","v2"))
 "geqNat#2"("v12","0"()) -> "True"()
 "geqNat#2"("0"(),"S"("v20")) -> "False"()
 "geqNat#2"("S"("v4"),"S"("v2")) -> "geqNat#2"("v4","v2")
 "eqNat#2"("0"(),"0"()) -> "True"()
 "eqNat#2"("S"("v16"),"0"()) -> "False"()
 "eqNat#2"("S"("v4"),"S"("v2")) -> "eqNat#2"("v4","v2")
 "eqNat#2"("0"(),"S"("v16")) -> "False"()
 "main"("v2","v1") -> "cond_sort_students_efficient_student_ids_course_ids"("quicksort#3"("greater_eq'_course_ids"("v2"),"mk_table#2"("v1","v2"),"v1")))


BEST_CASE(Omega(n^2),?)