WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).

(0) CpxRelTRS
(1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 213 ms]
(2) CpxRelTRS
(3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CpxRelTRS
(5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) typed CpxTrs
(7) OrderProof [LOWER BOUND(ID), 0 ms]
(8) typed CpxTrs
(9) RewriteLemmaProof [LOWER BOUND(ID), 1889 ms]
(10) typed CpxTrs
(11) RewriteLemmaProof [LOWER BOUND(ID), 99 ms]
(12) BEST
    (13) proven lower bound
        (14) LowerBoundPropagationProof [FINISHED, 0 ms]
        (15) BOUNDS(n^1, INF)
    (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 121 ms]
        (18) typed CpxTrs


----------------------------------------

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST
----------------------------------------

(1) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

(2)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST
----------------------------------------

(3) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(4)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   #less(@x, @y) -> #cklt(#compare(@x, @y))
   merge(@l1, @l2) -> merge#1(@l1, @l2)
   merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
   merge#1(nil, @l2) -> @l2
   merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
   merge#2(nil, @x, @xs) -> ::(@x, @xs)
   merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
   merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
   mergesort(@l) -> mergesort#1(@l)
   mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
   mergesort#1(nil) -> nil
   mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
   mergesort#2(nil, @x1) -> ::(@x1, nil)
   mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
   msplit(@l) -> msplit#1(@l)
   msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
   msplit#1(nil) -> tuple#2(nil, nil)
   msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
   msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
   msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))

The (relative) TRS S consists of the following rules:

   #cklt(#EQ) -> #false
   #cklt(#GT) -> #false
   #cklt(#LT) -> #true
   #compare(#0, #0) -> #EQ
   #compare(#0, #neg(@y)) -> #GT
   #compare(#0, #pos(@y)) -> #LT
   #compare(#0, #s(@y)) -> #LT
   #compare(#neg(@x), #0) -> #LT
   #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
   #compare(#neg(@x), #pos(@y)) -> #LT
   #compare(#pos(@x), #0) -> #GT
   #compare(#pos(@x), #neg(@y)) -> #GT
   #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
   #compare(#s(@x), #0) -> #GT
   #compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Rewrite Strategy: INNERMOST
----------------------------------------

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(6)
Obligation:
Innermost TRS:
Rules:
#less(@x, @y) -> #cklt(#compare(@x, @y))
merge(@l1, @l2) -> merge#1(@l1, @l2)
merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
merge#1(nil, @l2) -> @l2
merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
merge#2(nil, @x, @xs) -> ::(@x, @xs)
merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
mergesort(@l) -> mergesort#1(@l)
mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
mergesort#1(nil) -> nil
mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
mergesort#2(nil, @x1) -> ::(@x1, nil)
mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
msplit(@l) -> msplit#1(@l)
msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
msplit#1(nil) -> tuple#2(nil, nil)
msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
#cklt(#EQ) -> #false
#cklt(#GT) -> #false
#cklt(#LT) -> #true
#compare(#0, #0) -> #EQ
#compare(#0, #neg(@y)) -> #GT
#compare(#0, #pos(@y)) -> #LT
#compare(#0, #s(@y)) -> #LT
#compare(#neg(@x), #0) -> #LT
#compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
#compare(#neg(@x), #pos(@y)) -> #LT
#compare(#pos(@x), #0) -> #GT
#compare(#pos(@x), #neg(@y)) -> #GT
#compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
#compare(#s(@x), #0) -> #GT
#compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Types:
#less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true
#cklt :: #EQ:#GT:#LT -> #false:#true
#compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT
merge :: :::nil -> :::nil -> :::nil
merge#1 :: :::nil -> :::nil -> :::nil
:: :: #0:#neg:#pos:#s -> :::nil -> :::nil
merge#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
nil :: :::nil
merge#3 :: #false:#true -> #0:#neg:#pos:#s -> :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
#false :: #false:#true
#true :: #false:#true
mergesort :: :::nil -> :::nil
mergesort#1 :: :::nil -> :::nil
mergesort#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil
mergesort#3 :: tuple#2 -> :::nil
msplit :: :::nil -> tuple#2
tuple#2 :: :::nil -> :::nil -> tuple#2
msplit#1 :: :::nil -> tuple#2
msplit#2 :: :::nil -> #0:#neg:#pos:#s -> tuple#2
msplit#3 :: tuple#2 -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> tuple#2
#EQ :: #EQ:#GT:#LT
#GT :: #EQ:#GT:#LT
#LT :: #EQ:#GT:#LT
#0 :: #0:#neg:#pos:#s
#neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
hole_#false:#true1_4 :: #false:#true
hole_#0:#neg:#pos:#s2_4 :: #0:#neg:#pos:#s
hole_#EQ:#GT:#LT3_4 :: #EQ:#GT:#LT
hole_:::nil4_4 :: :::nil
hole_tuple#25_4 :: tuple#2
gen_#0:#neg:#pos:#s6_4 :: Nat -> #0:#neg:#pos:#s
gen_:::nil7_4 :: Nat -> :::nil

----------------------------------------

(7) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
#compare, merge, merge#1, mergesort, mergesort#1, mergesort#3, msplit, msplit#1

They will be analysed ascendingly in the following order:
merge = merge#1
merge < mergesort#3
mergesort = mergesort#1
mergesort = mergesort#3
mergesort#1 = mergesort#3
msplit < mergesort#1
msplit = msplit#1

----------------------------------------

(8)
Obligation:
Innermost TRS:
Rules:
#less(@x, @y) -> #cklt(#compare(@x, @y))
merge(@l1, @l2) -> merge#1(@l1, @l2)
merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
merge#1(nil, @l2) -> @l2
merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
merge#2(nil, @x, @xs) -> ::(@x, @xs)
merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
mergesort(@l) -> mergesort#1(@l)
mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
mergesort#1(nil) -> nil
mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
mergesort#2(nil, @x1) -> ::(@x1, nil)
mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
msplit(@l) -> msplit#1(@l)
msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
msplit#1(nil) -> tuple#2(nil, nil)
msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
#cklt(#EQ) -> #false
#cklt(#GT) -> #false
#cklt(#LT) -> #true
#compare(#0, #0) -> #EQ
#compare(#0, #neg(@y)) -> #GT
#compare(#0, #pos(@y)) -> #LT
#compare(#0, #s(@y)) -> #LT
#compare(#neg(@x), #0) -> #LT
#compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
#compare(#neg(@x), #pos(@y)) -> #LT
#compare(#pos(@x), #0) -> #GT
#compare(#pos(@x), #neg(@y)) -> #GT
#compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
#compare(#s(@x), #0) -> #GT
#compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Types:
#less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true
#cklt :: #EQ:#GT:#LT -> #false:#true
#compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT
merge :: :::nil -> :::nil -> :::nil
merge#1 :: :::nil -> :::nil -> :::nil
:: :: #0:#neg:#pos:#s -> :::nil -> :::nil
merge#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
nil :: :::nil
merge#3 :: #false:#true -> #0:#neg:#pos:#s -> :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
#false :: #false:#true
#true :: #false:#true
mergesort :: :::nil -> :::nil
mergesort#1 :: :::nil -> :::nil
mergesort#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil
mergesort#3 :: tuple#2 -> :::nil
msplit :: :::nil -> tuple#2
tuple#2 :: :::nil -> :::nil -> tuple#2
msplit#1 :: :::nil -> tuple#2
msplit#2 :: :::nil -> #0:#neg:#pos:#s -> tuple#2
msplit#3 :: tuple#2 -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> tuple#2
#EQ :: #EQ:#GT:#LT
#GT :: #EQ:#GT:#LT
#LT :: #EQ:#GT:#LT
#0 :: #0:#neg:#pos:#s
#neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
hole_#false:#true1_4 :: #false:#true
hole_#0:#neg:#pos:#s2_4 :: #0:#neg:#pos:#s
hole_#EQ:#GT:#LT3_4 :: #EQ:#GT:#LT
hole_:::nil4_4 :: :::nil
hole_tuple#25_4 :: tuple#2
gen_#0:#neg:#pos:#s6_4 :: Nat -> #0:#neg:#pos:#s
gen_:::nil7_4 :: Nat -> :::nil


Generator Equations:
gen_#0:#neg:#pos:#s6_4(0) <=> #0
gen_#0:#neg:#pos:#s6_4(+(x, 1)) <=> #neg(gen_#0:#neg:#pos:#s6_4(x))
gen_:::nil7_4(0) <=> nil
gen_:::nil7_4(+(x, 1)) <=> ::(#0, gen_:::nil7_4(x))


The following defined symbols remain to be analysed:
#compare, merge, merge#1, mergesort, mergesort#1, mergesort#3, msplit, msplit#1

They will be analysed ascendingly in the following order:
merge = merge#1
merge < mergesort#3
mergesort = mergesort#1
mergesort = mergesort#3
mergesort#1 = mergesort#3
msplit < mergesort#1
msplit = msplit#1

----------------------------------------

(9) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
#compare(gen_#0:#neg:#pos:#s6_4(n9_4), gen_#0:#neg:#pos:#s6_4(n9_4)) -> #EQ, rt in Omega(0)

Induction Base:
#compare(gen_#0:#neg:#pos:#s6_4(0), gen_#0:#neg:#pos:#s6_4(0)) ->_R^Omega(0)
#EQ

Induction Step:
#compare(gen_#0:#neg:#pos:#s6_4(+(n9_4, 1)), gen_#0:#neg:#pos:#s6_4(+(n9_4, 1))) ->_R^Omega(0)
#compare(gen_#0:#neg:#pos:#s6_4(n9_4), gen_#0:#neg:#pos:#s6_4(n9_4)) ->_IH
#EQ

We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
----------------------------------------

(10)
Obligation:
Innermost TRS:
Rules:
#less(@x, @y) -> #cklt(#compare(@x, @y))
merge(@l1, @l2) -> merge#1(@l1, @l2)
merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
merge#1(nil, @l2) -> @l2
merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
merge#2(nil, @x, @xs) -> ::(@x, @xs)
merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
mergesort(@l) -> mergesort#1(@l)
mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
mergesort#1(nil) -> nil
mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
mergesort#2(nil, @x1) -> ::(@x1, nil)
mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
msplit(@l) -> msplit#1(@l)
msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
msplit#1(nil) -> tuple#2(nil, nil)
msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
#cklt(#EQ) -> #false
#cklt(#GT) -> #false
#cklt(#LT) -> #true
#compare(#0, #0) -> #EQ
#compare(#0, #neg(@y)) -> #GT
#compare(#0, #pos(@y)) -> #LT
#compare(#0, #s(@y)) -> #LT
#compare(#neg(@x), #0) -> #LT
#compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
#compare(#neg(@x), #pos(@y)) -> #LT
#compare(#pos(@x), #0) -> #GT
#compare(#pos(@x), #neg(@y)) -> #GT
#compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
#compare(#s(@x), #0) -> #GT
#compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Types:
#less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true
#cklt :: #EQ:#GT:#LT -> #false:#true
#compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT
merge :: :::nil -> :::nil -> :::nil
merge#1 :: :::nil -> :::nil -> :::nil
:: :: #0:#neg:#pos:#s -> :::nil -> :::nil
merge#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
nil :: :::nil
merge#3 :: #false:#true -> #0:#neg:#pos:#s -> :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
#false :: #false:#true
#true :: #false:#true
mergesort :: :::nil -> :::nil
mergesort#1 :: :::nil -> :::nil
mergesort#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil
mergesort#3 :: tuple#2 -> :::nil
msplit :: :::nil -> tuple#2
tuple#2 :: :::nil -> :::nil -> tuple#2
msplit#1 :: :::nil -> tuple#2
msplit#2 :: :::nil -> #0:#neg:#pos:#s -> tuple#2
msplit#3 :: tuple#2 -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> tuple#2
#EQ :: #EQ:#GT:#LT
#GT :: #EQ:#GT:#LT
#LT :: #EQ:#GT:#LT
#0 :: #0:#neg:#pos:#s
#neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
hole_#false:#true1_4 :: #false:#true
hole_#0:#neg:#pos:#s2_4 :: #0:#neg:#pos:#s
hole_#EQ:#GT:#LT3_4 :: #EQ:#GT:#LT
hole_:::nil4_4 :: :::nil
hole_tuple#25_4 :: tuple#2
gen_#0:#neg:#pos:#s6_4 :: Nat -> #0:#neg:#pos:#s
gen_:::nil7_4 :: Nat -> :::nil


Lemmas:
#compare(gen_#0:#neg:#pos:#s6_4(n9_4), gen_#0:#neg:#pos:#s6_4(n9_4)) -> #EQ, rt in Omega(0)


Generator Equations:
gen_#0:#neg:#pos:#s6_4(0) <=> #0
gen_#0:#neg:#pos:#s6_4(+(x, 1)) <=> #neg(gen_#0:#neg:#pos:#s6_4(x))
gen_:::nil7_4(0) <=> nil
gen_:::nil7_4(+(x, 1)) <=> ::(#0, gen_:::nil7_4(x))


The following defined symbols remain to be analysed:
msplit#1, merge, merge#1, mergesort, mergesort#1, mergesort#3, msplit

They will be analysed ascendingly in the following order:
merge = merge#1
merge < mergesort#3
mergesort = mergesort#1
mergesort = mergesort#3
mergesort#1 = mergesort#3
msplit < mergesort#1
msplit = msplit#1

----------------------------------------

(11) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
msplit#1(gen_:::nil7_4(*(2, n318704_4))) -> tuple#2(gen_:::nil7_4(n318704_4), gen_:::nil7_4(n318704_4)), rt in Omega(1 + n318704_4)

Induction Base:
msplit#1(gen_:::nil7_4(*(2, 0))) ->_R^Omega(1)
tuple#2(nil, nil)

Induction Step:
msplit#1(gen_:::nil7_4(*(2, +(n318704_4, 1)))) ->_R^Omega(1)
msplit#2(gen_:::nil7_4(+(1, *(2, n318704_4))), #0) ->_R^Omega(1)
msplit#3(msplit(gen_:::nil7_4(*(2, n318704_4))), #0, #0) ->_R^Omega(1)
msplit#3(msplit#1(gen_:::nil7_4(*(2, n318704_4))), #0, #0) ->_IH
msplit#3(tuple#2(gen_:::nil7_4(c318705_4), gen_:::nil7_4(c318705_4)), #0, #0) ->_R^Omega(1)
tuple#2(::(#0, gen_:::nil7_4(n318704_4)), ::(#0, gen_:::nil7_4(n318704_4)))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(12)
Complex Obligation (BEST)

----------------------------------------

(13)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
#less(@x, @y) -> #cklt(#compare(@x, @y))
merge(@l1, @l2) -> merge#1(@l1, @l2)
merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
merge#1(nil, @l2) -> @l2
merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
merge#2(nil, @x, @xs) -> ::(@x, @xs)
merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
mergesort(@l) -> mergesort#1(@l)
mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
mergesort#1(nil) -> nil
mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
mergesort#2(nil, @x1) -> ::(@x1, nil)
mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
msplit(@l) -> msplit#1(@l)
msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
msplit#1(nil) -> tuple#2(nil, nil)
msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
#cklt(#EQ) -> #false
#cklt(#GT) -> #false
#cklt(#LT) -> #true
#compare(#0, #0) -> #EQ
#compare(#0, #neg(@y)) -> #GT
#compare(#0, #pos(@y)) -> #LT
#compare(#0, #s(@y)) -> #LT
#compare(#neg(@x), #0) -> #LT
#compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
#compare(#neg(@x), #pos(@y)) -> #LT
#compare(#pos(@x), #0) -> #GT
#compare(#pos(@x), #neg(@y)) -> #GT
#compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
#compare(#s(@x), #0) -> #GT
#compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Types:
#less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true
#cklt :: #EQ:#GT:#LT -> #false:#true
#compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT
merge :: :::nil -> :::nil -> :::nil
merge#1 :: :::nil -> :::nil -> :::nil
:: :: #0:#neg:#pos:#s -> :::nil -> :::nil
merge#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
nil :: :::nil
merge#3 :: #false:#true -> #0:#neg:#pos:#s -> :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
#false :: #false:#true
#true :: #false:#true
mergesort :: :::nil -> :::nil
mergesort#1 :: :::nil -> :::nil
mergesort#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil
mergesort#3 :: tuple#2 -> :::nil
msplit :: :::nil -> tuple#2
tuple#2 :: :::nil -> :::nil -> tuple#2
msplit#1 :: :::nil -> tuple#2
msplit#2 :: :::nil -> #0:#neg:#pos:#s -> tuple#2
msplit#3 :: tuple#2 -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> tuple#2
#EQ :: #EQ:#GT:#LT
#GT :: #EQ:#GT:#LT
#LT :: #EQ:#GT:#LT
#0 :: #0:#neg:#pos:#s
#neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
hole_#false:#true1_4 :: #false:#true
hole_#0:#neg:#pos:#s2_4 :: #0:#neg:#pos:#s
hole_#EQ:#GT:#LT3_4 :: #EQ:#GT:#LT
hole_:::nil4_4 :: :::nil
hole_tuple#25_4 :: tuple#2
gen_#0:#neg:#pos:#s6_4 :: Nat -> #0:#neg:#pos:#s
gen_:::nil7_4 :: Nat -> :::nil


Lemmas:
#compare(gen_#0:#neg:#pos:#s6_4(n9_4), gen_#0:#neg:#pos:#s6_4(n9_4)) -> #EQ, rt in Omega(0)


Generator Equations:
gen_#0:#neg:#pos:#s6_4(0) <=> #0
gen_#0:#neg:#pos:#s6_4(+(x, 1)) <=> #neg(gen_#0:#neg:#pos:#s6_4(x))
gen_:::nil7_4(0) <=> nil
gen_:::nil7_4(+(x, 1)) <=> ::(#0, gen_:::nil7_4(x))


The following defined symbols remain to be analysed:
msplit#1, merge, merge#1, mergesort, mergesort#1, mergesort#3, msplit

They will be analysed ascendingly in the following order:
merge = merge#1
merge < mergesort#3
mergesort = mergesort#1
mergesort = mergesort#3
mergesort#1 = mergesort#3
msplit < mergesort#1
msplit = msplit#1

----------------------------------------

(14) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(15)
BOUNDS(n^1, INF)

----------------------------------------

(16)
Obligation:
Innermost TRS:
Rules:
#less(@x, @y) -> #cklt(#compare(@x, @y))
merge(@l1, @l2) -> merge#1(@l1, @l2)
merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
merge#1(nil, @l2) -> @l2
merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
merge#2(nil, @x, @xs) -> ::(@x, @xs)
merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
mergesort(@l) -> mergesort#1(@l)
mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
mergesort#1(nil) -> nil
mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
mergesort#2(nil, @x1) -> ::(@x1, nil)
mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
msplit(@l) -> msplit#1(@l)
msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
msplit#1(nil) -> tuple#2(nil, nil)
msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
#cklt(#EQ) -> #false
#cklt(#GT) -> #false
#cklt(#LT) -> #true
#compare(#0, #0) -> #EQ
#compare(#0, #neg(@y)) -> #GT
#compare(#0, #pos(@y)) -> #LT
#compare(#0, #s(@y)) -> #LT
#compare(#neg(@x), #0) -> #LT
#compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
#compare(#neg(@x), #pos(@y)) -> #LT
#compare(#pos(@x), #0) -> #GT
#compare(#pos(@x), #neg(@y)) -> #GT
#compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
#compare(#s(@x), #0) -> #GT
#compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Types:
#less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true
#cklt :: #EQ:#GT:#LT -> #false:#true
#compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT
merge :: :::nil -> :::nil -> :::nil
merge#1 :: :::nil -> :::nil -> :::nil
:: :: #0:#neg:#pos:#s -> :::nil -> :::nil
merge#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
nil :: :::nil
merge#3 :: #false:#true -> #0:#neg:#pos:#s -> :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
#false :: #false:#true
#true :: #false:#true
mergesort :: :::nil -> :::nil
mergesort#1 :: :::nil -> :::nil
mergesort#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil
mergesort#3 :: tuple#2 -> :::nil
msplit :: :::nil -> tuple#2
tuple#2 :: :::nil -> :::nil -> tuple#2
msplit#1 :: :::nil -> tuple#2
msplit#2 :: :::nil -> #0:#neg:#pos:#s -> tuple#2
msplit#3 :: tuple#2 -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> tuple#2
#EQ :: #EQ:#GT:#LT
#GT :: #EQ:#GT:#LT
#LT :: #EQ:#GT:#LT
#0 :: #0:#neg:#pos:#s
#neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
hole_#false:#true1_4 :: #false:#true
hole_#0:#neg:#pos:#s2_4 :: #0:#neg:#pos:#s
hole_#EQ:#GT:#LT3_4 :: #EQ:#GT:#LT
hole_:::nil4_4 :: :::nil
hole_tuple#25_4 :: tuple#2
gen_#0:#neg:#pos:#s6_4 :: Nat -> #0:#neg:#pos:#s
gen_:::nil7_4 :: Nat -> :::nil


Lemmas:
#compare(gen_#0:#neg:#pos:#s6_4(n9_4), gen_#0:#neg:#pos:#s6_4(n9_4)) -> #EQ, rt in Omega(0)
msplit#1(gen_:::nil7_4(*(2, n318704_4))) -> tuple#2(gen_:::nil7_4(n318704_4), gen_:::nil7_4(n318704_4)), rt in Omega(1 + n318704_4)


Generator Equations:
gen_#0:#neg:#pos:#s6_4(0) <=> #0
gen_#0:#neg:#pos:#s6_4(+(x, 1)) <=> #neg(gen_#0:#neg:#pos:#s6_4(x))
gen_:::nil7_4(0) <=> nil
gen_:::nil7_4(+(x, 1)) <=> ::(#0, gen_:::nil7_4(x))


The following defined symbols remain to be analysed:
msplit, merge, merge#1, mergesort, mergesort#1, mergesort#3

They will be analysed ascendingly in the following order:
merge = merge#1
merge < mergesort#3
mergesort = mergesort#1
mergesort = mergesort#3
mergesort#1 = mergesort#3
msplit < mergesort#1
msplit = msplit#1

----------------------------------------

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
merge#1(gen_:::nil7_4(1), gen_:::nil7_4(n319598_4)) -> gen_:::nil7_4(+(1, n319598_4)), rt in Omega(1 + n319598_4)

Induction Base:
merge#1(gen_:::nil7_4(1), gen_:::nil7_4(0)) ->_R^Omega(1)
merge#2(gen_:::nil7_4(0), #0, gen_:::nil7_4(0)) ->_R^Omega(1)
::(#0, gen_:::nil7_4(0))

Induction Step:
merge#1(gen_:::nil7_4(1), gen_:::nil7_4(+(n319598_4, 1))) ->_R^Omega(1)
merge#2(gen_:::nil7_4(+(n319598_4, 1)), #0, gen_:::nil7_4(0)) ->_R^Omega(1)
merge#3(#less(#0, #0), #0, gen_:::nil7_4(0), #0, gen_:::nil7_4(n319598_4)) ->_R^Omega(1)
merge#3(#cklt(#compare(#0, #0)), #0, gen_:::nil7_4(0), #0, gen_:::nil7_4(n319598_4)) ->_L^Omega(0)
merge#3(#cklt(#EQ), #0, gen_:::nil7_4(0), #0, gen_:::nil7_4(n319598_4)) ->_R^Omega(0)
merge#3(#false, #0, gen_:::nil7_4(0), #0, gen_:::nil7_4(n319598_4)) ->_R^Omega(1)
::(#0, merge(::(#0, gen_:::nil7_4(0)), gen_:::nil7_4(n319598_4))) ->_R^Omega(1)
::(#0, merge#1(::(#0, gen_:::nil7_4(0)), gen_:::nil7_4(n319598_4))) ->_IH
::(#0, gen_:::nil7_4(+(1, c319599_4)))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(18)
Obligation:
Innermost TRS:
Rules:
#less(@x, @y) -> #cklt(#compare(@x, @y))
merge(@l1, @l2) -> merge#1(@l1, @l2)
merge#1(::(@x, @xs), @l2) -> merge#2(@l2, @x, @xs)
merge#1(nil, @l2) -> @l2
merge#2(::(@y, @ys), @x, @xs) -> merge#3(#less(@x, @y), @x, @xs, @y, @ys)
merge#2(nil, @x, @xs) -> ::(@x, @xs)
merge#3(#false, @x, @xs, @y, @ys) -> ::(@y, merge(::(@x, @xs), @ys))
merge#3(#true, @x, @xs, @y, @ys) -> ::(@x, merge(@xs, ::(@y, @ys)))
mergesort(@l) -> mergesort#1(@l)
mergesort#1(::(@x1, @xs)) -> mergesort#2(@xs, @x1)
mergesort#1(nil) -> nil
mergesort#2(::(@x2, @xs'), @x1) -> mergesort#3(msplit(::(@x1, ::(@x2, @xs'))))
mergesort#2(nil, @x1) -> ::(@x1, nil)
mergesort#3(tuple#2(@l1, @l2)) -> merge(mergesort(@l1), mergesort(@l2))
msplit(@l) -> msplit#1(@l)
msplit#1(::(@x1, @xs)) -> msplit#2(@xs, @x1)
msplit#1(nil) -> tuple#2(nil, nil)
msplit#2(::(@x2, @xs'), @x1) -> msplit#3(msplit(@xs'), @x1, @x2)
msplit#2(nil, @x1) -> tuple#2(::(@x1, nil), nil)
msplit#3(tuple#2(@l1, @l2), @x1, @x2) -> tuple#2(::(@x1, @l1), ::(@x2, @l2))
#cklt(#EQ) -> #false
#cklt(#GT) -> #false
#cklt(#LT) -> #true
#compare(#0, #0) -> #EQ
#compare(#0, #neg(@y)) -> #GT
#compare(#0, #pos(@y)) -> #LT
#compare(#0, #s(@y)) -> #LT
#compare(#neg(@x), #0) -> #LT
#compare(#neg(@x), #neg(@y)) -> #compare(@y, @x)
#compare(#neg(@x), #pos(@y)) -> #LT
#compare(#pos(@x), #0) -> #GT
#compare(#pos(@x), #neg(@y)) -> #GT
#compare(#pos(@x), #pos(@y)) -> #compare(@x, @y)
#compare(#s(@x), #0) -> #GT
#compare(#s(@x), #s(@y)) -> #compare(@x, @y)

Types:
#less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true
#cklt :: #EQ:#GT:#LT -> #false:#true
#compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT
merge :: :::nil -> :::nil -> :::nil
merge#1 :: :::nil -> :::nil -> :::nil
:: :: #0:#neg:#pos:#s -> :::nil -> :::nil
merge#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
nil :: :::nil
merge#3 :: #false:#true -> #0:#neg:#pos:#s -> :::nil -> #0:#neg:#pos:#s -> :::nil -> :::nil
#false :: #false:#true
#true :: #false:#true
mergesort :: :::nil -> :::nil
mergesort#1 :: :::nil -> :::nil
mergesort#2 :: :::nil -> #0:#neg:#pos:#s -> :::nil
mergesort#3 :: tuple#2 -> :::nil
msplit :: :::nil -> tuple#2
tuple#2 :: :::nil -> :::nil -> tuple#2
msplit#1 :: :::nil -> tuple#2
msplit#2 :: :::nil -> #0:#neg:#pos:#s -> tuple#2
msplit#3 :: tuple#2 -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> tuple#2
#EQ :: #EQ:#GT:#LT
#GT :: #EQ:#GT:#LT
#LT :: #EQ:#GT:#LT
#0 :: #0:#neg:#pos:#s
#neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
#s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s
hole_#false:#true1_4 :: #false:#true
hole_#0:#neg:#pos:#s2_4 :: #0:#neg:#pos:#s
hole_#EQ:#GT:#LT3_4 :: #EQ:#GT:#LT
hole_:::nil4_4 :: :::nil
hole_tuple#25_4 :: tuple#2
gen_#0:#neg:#pos:#s6_4 :: Nat -> #0:#neg:#pos:#s
gen_:::nil7_4 :: Nat -> :::nil


Lemmas:
#compare(gen_#0:#neg:#pos:#s6_4(n9_4), gen_#0:#neg:#pos:#s6_4(n9_4)) -> #EQ, rt in Omega(0)
msplit#1(gen_:::nil7_4(*(2, n318704_4))) -> tuple#2(gen_:::nil7_4(n318704_4), gen_:::nil7_4(n318704_4)), rt in Omega(1 + n318704_4)
merge#1(gen_:::nil7_4(1), gen_:::nil7_4(n319598_4)) -> gen_:::nil7_4(+(1, n319598_4)), rt in Omega(1 + n319598_4)


Generator Equations:
gen_#0:#neg:#pos:#s6_4(0) <=> #0
gen_#0:#neg:#pos:#s6_4(+(x, 1)) <=> #neg(gen_#0:#neg:#pos:#s6_4(x))
gen_:::nil7_4(0) <=> nil
gen_:::nil7_4(+(x, 1)) <=> ::(#0, gen_:::nil7_4(x))


The following defined symbols remain to be analysed:
merge, mergesort, mergesort#1, mergesort#3

They will be analysed ascendingly in the following order:
merge = merge#1
merge < mergesort#3
mergesort = mergesort#1
mergesort = mergesort#3
mergesort#1 = mergesort#3