/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


WORST_CASE(Omega(n^2), O(n^3))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3).

(0) CpxTRS
(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxWeightedTrs
    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxTypedWeightedTrs
    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
    (6) CpxTypedWeightedCompleteTrs
    (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxTypedWeightedCompleteTrs
    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (10) CpxRNTS
    (11) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CpxRNTS
    (13) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CpxRNTS
    (15) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (16) CpxRNTS
    (17) IntTrsBoundProof [UPPER BOUND(ID), 314 ms]
    (18) CpxRNTS
    (19) IntTrsBoundProof [UPPER BOUND(ID), 159 ms]
    (20) CpxRNTS
    (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (22) CpxRNTS
    (23) IntTrsBoundProof [UPPER BOUND(ID), 372 ms]
    (24) CpxRNTS
    (25) IntTrsBoundProof [UPPER BOUND(ID), 185 ms]
    (26) CpxRNTS
    (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (28) CpxRNTS
    (29) IntTrsBoundProof [UPPER BOUND(ID), 943 ms]
    (30) CpxRNTS
    (31) IntTrsBoundProof [UPPER BOUND(ID), 213 ms]
    (32) CpxRNTS
    (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (34) CpxRNTS
    (35) IntTrsBoundProof [UPPER BOUND(ID), 1664 ms]
    (36) CpxRNTS
    (37) IntTrsBoundProof [UPPER BOUND(ID), 483 ms]
    (38) CpxRNTS
    (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (40) CpxRNTS
    (41) IntTrsBoundProof [UPPER BOUND(ID), 604 ms]
    (42) CpxRNTS
    (43) IntTrsBoundProof [UPPER BOUND(ID), 175 ms]
    (44) CpxRNTS
    (45) FinalProof [FINISHED, 0 ms]
    (46) BOUNDS(1, n^3)
(47) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(48) CpxTRS
    (49) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (50) typed CpxTrs
    (51) OrderProof [LOWER BOUND(ID), 0 ms]
    (52) typed CpxTrs
    (53) RewriteLemmaProof [LOWER BOUND(ID), 259 ms]
    (54) BEST
        (55) proven lower bound
            (56) LowerBoundPropagationProof [FINISHED, 0 ms]
            (57) BOUNDS(n^1, INF)
        (58) typed CpxTrs
            (59) RewriteLemmaProof [LOWER BOUND(ID), 51 ms]
            (60) typed CpxTrs
            (61) RewriteLemmaProof [LOWER BOUND(ID), 32 ms]
            (62) typed CpxTrs
            (63) RewriteLemmaProof [LOWER BOUND(ID), 864 ms]
            (64) proven lower bound
            (65) LowerBoundPropagationProof [FINISHED, 0 ms]
            (66) BOUNDS(n^2, INF)


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

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3).


The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(m)) -> false
   eq(s(n), 0) -> false
   eq(s(n), s(m)) -> eq(n, m)
   le(0, m) -> true
   le(s(n), 0) -> false
   le(s(n), s(m)) -> le(n, m)
   min(cons(0, nil)) -> 0
   min(cons(s(n), nil)) -> s(n)
   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
   replace(n, m, nil) -> nil
   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
   if_replace(true, n, m, cons(k, x)) -> cons(m, x)
   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
   sort(nil) -> nil
   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

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


The TRS R consists of the following rules:

   eq(0, 0) -> true [1]
   eq(0, s(m)) -> false [1]
   eq(s(n), 0) -> false [1]
   eq(s(n), s(m)) -> eq(n, m) [1]
   le(0, m) -> true [1]
   le(s(n), 0) -> false [1]
   le(s(n), s(m)) -> le(n, m) [1]
   min(cons(0, nil)) -> 0 [1]
   min(cons(s(n), nil)) -> s(n) [1]
   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) [1]
   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
   replace(n, m, nil) -> nil [1]
   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) [1]
   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
   sort(nil) -> nil [1]
   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) [1]

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

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

(4)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   eq(0, 0) -> true [1]
   eq(0, s(m)) -> false [1]
   eq(s(n), 0) -> false [1]
   eq(s(n), s(m)) -> eq(n, m) [1]
   le(0, m) -> true [1]
   le(s(n), 0) -> false [1]
   le(s(n), s(m)) -> le(n, m) [1]
   min(cons(0, nil)) -> 0 [1]
   min(cons(s(n), nil)) -> s(n) [1]
   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) [1]
   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
   replace(n, m, nil) -> nil [1]
   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) [1]
   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
   sort(nil) -> nil [1]
   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) [1]

The TRS has the following type information:
eq :: 0:s -> 0:s -> true:false
0 :: 0:s
true :: true:false
s :: 0:s -> 0:s
false :: true:false
le :: 0:s -> 0:s -> true:false
min :: nil:cons -> 0:s
cons :: 0:s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0:s
replace :: 0:s -> 0:s -> nil:cons -> nil:cons
if_replace :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons

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

(5) CompletionProof (UPPER BOUND(ID))
The transformation into a RNTS is sound, since:

(a) The obligation is a constructor system where every type has a constant constructor,

(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:

   sort_1

(c) The following functions are completely defined:

   replace_3
   min_1
   eq_2
   le_2
   if_replace_4
   if_min_2

Due to the following rules being added:

   min(v0) -> 0 [0]
   if_replace(v0, v1, v2, v3) -> nil [0]
   if_min(v0, v1) -> 0 [0]

And the following fresh constants: none

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

(6)
Obligation:
Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   eq(0, 0) -> true [1]
   eq(0, s(m)) -> false [1]
   eq(s(n), 0) -> false [1]
   eq(s(n), s(m)) -> eq(n, m) [1]
   le(0, m) -> true [1]
   le(s(n), 0) -> false [1]
   le(s(n), s(m)) -> le(n, m) [1]
   min(cons(0, nil)) -> 0 [1]
   min(cons(s(n), nil)) -> s(n) [1]
   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) [1]
   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
   replace(n, m, nil) -> nil [1]
   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) [1]
   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
   sort(nil) -> nil [1]
   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) [1]
   min(v0) -> 0 [0]
   if_replace(v0, v1, v2, v3) -> nil [0]
   if_min(v0, v1) -> 0 [0]

The TRS has the following type information:
eq :: 0:s -> 0:s -> true:false
0 :: 0:s
true :: true:false
s :: 0:s -> 0:s
false :: true:false
le :: 0:s -> 0:s -> true:false
min :: nil:cons -> 0:s
cons :: 0:s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0:s
replace :: 0:s -> 0:s -> nil:cons -> nil:cons
if_replace :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons

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

(7) NarrowingProof (BOTH BOUNDS(ID, ID))
Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
----------------------------------------

(8)
Obligation:
Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   eq(0, 0) -> true [1]
   eq(0, s(m)) -> false [1]
   eq(s(n), 0) -> false [1]
   eq(s(n), s(m)) -> eq(n, m) [1]
   le(0, m) -> true [1]
   le(s(n), 0) -> false [1]
   le(s(n), s(m)) -> le(n, m) [1]
   min(cons(0, nil)) -> 0 [1]
   min(cons(s(n), nil)) -> s(n) [1]
   min(cons(0, cons(m, x))) -> if_min(true, cons(0, cons(m, x))) [2]
   min(cons(s(n'), cons(0, x))) -> if_min(false, cons(s(n'), cons(0, x))) [2]
   min(cons(s(n''), cons(s(m'), x))) -> if_min(le(n'', m'), cons(s(n''), cons(s(m'), x))) [2]
   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
   replace(n, m, nil) -> nil [1]
   replace(0, m, cons(0, x)) -> if_replace(true, 0, m, cons(0, x)) [2]
   replace(0, m, cons(s(m''), x)) -> if_replace(false, 0, m, cons(s(m''), x)) [2]
   replace(s(n1), m, cons(0, x)) -> if_replace(false, s(n1), m, cons(0, x)) [2]
   replace(s(n2), m, cons(s(m1), x)) -> if_replace(eq(n2, m1), s(n2), m, cons(s(m1), x)) [2]
   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
   sort(nil) -> nil [1]
   sort(cons(0, nil)) -> cons(min(cons(0, nil)), sort(replace(0, 0, nil))) [2]
   sort(cons(s(n3), nil)) -> cons(min(cons(s(n3), nil)), sort(replace(s(n3), s(n3), nil))) [2]
   sort(cons(n, cons(m2, x'))) -> cons(min(cons(n, cons(m2, x'))), sort(replace(if_min(le(n, m2), cons(n, cons(m2, x'))), n, cons(m2, x')))) [2]
   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(0, n, x))) [1]
   min(v0) -> 0 [0]
   if_replace(v0, v1, v2, v3) -> nil [0]
   if_min(v0, v1) -> 0 [0]

The TRS has the following type information:
eq :: 0:s -> 0:s -> true:false
0 :: 0:s
true :: true:false
s :: 0:s -> 0:s
false :: true:false
le :: 0:s -> 0:s -> true:false
min :: nil:cons -> 0:s
cons :: 0:s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0:s
replace :: 0:s -> 0:s -> nil:cons -> nil:cons
if_replace :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons

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

(9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   0 => 0
   true => 1
   false => 0
   nil => 0

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

(10)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(n, m) :|: n >= 0, z' = 1 + m, z = 1 + n, m >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' = 1 + m, m >= 0
   eq(z, z') -{ 1 }-> 0 :|: n >= 0, z = 1 + n, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(n, m, x) :|: n >= 0, x >= 0, z1 = 1 + k + x, z' = n, k >= 0, z = 0, z'' = m, m >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + m + x :|: n >= 0, z = 1, x >= 0, z1 = 1 + k + x, z' = n, k >= 0, z'' = m, m >= 0
   le(z, z') -{ 1 }-> le(n, m) :|: n >= 0, z' = 1 + m, z = 1 + n, m >= 0
   le(z, z') -{ 1 }-> 1 :|: z' = m, z = 0, m >= 0
   le(z, z') -{ 1 }-> 0 :|: n >= 0, z = 1 + n, z' = 0
   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   min(z) -{ 1 }-> 1 + n :|: z = 1 + (1 + n) + 0, n >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(n2, m1), 1 + n2, m, 1 + (1 + m1) + x) :|: z = 1 + n2, z' = m, z'' = 1 + (1 + m1) + x, x >= 0, n2 >= 0, m1 >= 0, m >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, m, 1 + 0 + x) :|: z' = m, x >= 0, z = 0, z'' = 1 + 0 + x, m >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, m, 1 + (1 + m'') + x) :|: z' = m, m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, m >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + n1, m, 1 + 0 + x) :|: z = 1 + n1, z' = m, x >= 0, n1 >= 0, z'' = 1 + 0 + x, m >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, n >= 0, z = n, z' = m, m >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + n3) + 0) + sort(replace(1 + n3, 1 + n3, 0)) :|: z = 1 + (1 + n3) + 0, n3 >= 0


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

(11) SimplificationProof (BOTH BOUNDS(ID, ID))
Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
----------------------------------------

(12)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0


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

(13) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
Found the following analysis order by SCC decomposition:

   { le }
   { eq }
   { min, if_min }
   { replace, if_replace }
   { sort }

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

(14)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {le}, {eq}, {min,if_min}, {replace,if_replace}, {sort}

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

(15) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(16)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {le}, {eq}, {min,if_min}, {replace,if_replace}, {sort}

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

(17) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: le
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 1

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

(18)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {le}, {eq}, {min,if_min}, {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: ?, size: O(1) [1]

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

(19) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: le
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 2 + z'

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

(20)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {eq}, {min,if_min}, {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]

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

(21) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(22)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {eq}, {min,if_min}, {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]

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

(23) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: eq
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 1

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

(24)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {eq}, {min,if_min}, {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: ?, size: O(1) [1]

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

(25) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: eq
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 3 + z'

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

(26)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {min,if_min}, {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]

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

(27) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(28)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {min,if_min}, {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]

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

(29) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using KoAT for: min
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z

Computed SIZE bound using KoAT for: if_min
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z'

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

(30)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {min,if_min}, {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: ?, size: O(n^1) [z]
  if_min: runtime: ?, size: O(n^1) [z']

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

(31) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: min
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 5 + 4*z + z^2

Computed RUNTIME bound using KoAT for: if_min
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 22 + 24*z' + 8*z'^2

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

(32)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0

Function symbols to be analyzed: {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']

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

(33) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(34)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 123 + 65*m2 + 18*m2*n + 18*m2*x' + 9*m2^2 + 64*n + 18*n*x' + 9*n^2 + 64*x' + 9*x'^2 }-> 1 + s10 + sort(replace(s11, n, 1 + m2 + x')) :|: s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> 1 + s12 + sort(replace(0, n, x)) :|: s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 12 }-> 1 + s8 + sort(replace(0, 0, 0)) :|: s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
   sort(z) -{ 7 + 4*z + z^2 }-> 1 + s9 + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0

Function symbols to be analyzed: {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']

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

(35) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using KoAT for: replace
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z' + z''

Computed SIZE bound using CoFloCo for: if_replace
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z'' + z1

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

(36)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 123 + 65*m2 + 18*m2*n + 18*m2*x' + 9*m2^2 + 64*n + 18*n*x' + 9*n^2 + 64*x' + 9*x'^2 }-> 1 + s10 + sort(replace(s11, n, 1 + m2 + x')) :|: s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> 1 + s12 + sort(replace(0, n, x)) :|: s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 12 }-> 1 + s8 + sort(replace(0, 0, 0)) :|: s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
   sort(z) -{ 7 + 4*z + z^2 }-> 1 + s9 + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0

Function symbols to be analyzed: {replace,if_replace}, {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
  replace: runtime: ?, size: O(n^1) [z' + z'']
  if_replace: runtime: ?, size: O(n^1) [z'' + z1]

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

(37) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: replace
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 6 + 5*z'' + z''^2

Computed RUNTIME bound using KoAT for: if_replace
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 8 + 5*z1 + z1^2

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

(38)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 123 + 65*m2 + 18*m2*n + 18*m2*x' + 9*m2^2 + 64*n + 18*n*x' + 9*n^2 + 64*x' + 9*x'^2 }-> 1 + s10 + sort(replace(s11, n, 1 + m2 + x')) :|: s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> 1 + s12 + sort(replace(0, n, x)) :|: s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 12 }-> 1 + s8 + sort(replace(0, 0, 0)) :|: s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
   sort(z) -{ 7 + 4*z + z^2 }-> 1 + s9 + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0

Function symbols to be analyzed: {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]

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

(39) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(40)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 7 + 5*x + x^2 }-> 1 + k + s17 :|: s17 >= 0, s17 <= z'' + x, z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s13 :|: s13 >= 0, s13 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 24 + 9*m'' + 2*m''*x + m''^2 + 9*x + x^2 }-> s14 :|: s14 >= 0, s14 <= z' + (1 + (1 + m'') + x), m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s15 :|: s15 >= 0, s15 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 27 + 10*m1 + 2*m1*x + m1^2 + 9*x + x^2 }-> s16 :|: s16 >= 0, s16 <= z' + (1 + (1 + m1) + x), s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 135 + 72*m2 + 18*m2*n + 20*m2*x' + 10*m2^2 + 64*n + 18*n*x' + 9*n^2 + 71*x' + 10*x'^2 }-> 1 + s10 + sort(s20) :|: s20 >= 0, s20 <= n + (1 + m2 + x'), s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 17 + 6*n + 2*n*x + n^2 + 11*x + 2*x^2 }-> 1 + s12 + sort(s21) :|: s21 >= 0, s21 <= n + x, s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 18 }-> 1 + s8 + sort(s18) :|: s18 >= 0, s18 <= 0 + 0, s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
   sort(z) -{ 13 + 4*z + z^2 }-> 1 + s9 + sort(s19) :|: s19 >= 0, s19 <= 1 + (z - 2) + 0, s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0

Function symbols to be analyzed: {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]

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

(41) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: sort
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: z + z^2

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

(42)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 7 + 5*x + x^2 }-> 1 + k + s17 :|: s17 >= 0, s17 <= z'' + x, z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s13 :|: s13 >= 0, s13 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 24 + 9*m'' + 2*m''*x + m''^2 + 9*x + x^2 }-> s14 :|: s14 >= 0, s14 <= z' + (1 + (1 + m'') + x), m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s15 :|: s15 >= 0, s15 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 27 + 10*m1 + 2*m1*x + m1^2 + 9*x + x^2 }-> s16 :|: s16 >= 0, s16 <= z' + (1 + (1 + m1) + x), s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 135 + 72*m2 + 18*m2*n + 20*m2*x' + 10*m2^2 + 64*n + 18*n*x' + 9*n^2 + 71*x' + 10*x'^2 }-> 1 + s10 + sort(s20) :|: s20 >= 0, s20 <= n + (1 + m2 + x'), s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 17 + 6*n + 2*n*x + n^2 + 11*x + 2*x^2 }-> 1 + s12 + sort(s21) :|: s21 >= 0, s21 <= n + x, s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 18 }-> 1 + s8 + sort(s18) :|: s18 >= 0, s18 <= 0 + 0, s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
   sort(z) -{ 13 + 4*z + z^2 }-> 1 + s9 + sort(s19) :|: s19 >= 0, s19 <= 1 + (z - 2) + 0, s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0

Function symbols to be analyzed: {sort}
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]
  sort: runtime: ?, size: O(n^2) [z + z^2]

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

(43) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: sort
after applying outer abstraction to obtain an ITS,
resulting in: O(n^3) with polynomial bound: 1 + 183*z + 228*z^2 + 91*z^3

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

(44)
Obligation:
Complexity RNTS consisting of the following rules:

   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
   if_replace(z, z', z'', z1) -{ 7 + 5*x + x^2 }-> 1 + k + s17 :|: s17 >= 0, s17 <= z'' + x, z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: z >= 0
   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s13 :|: s13 >= 0, s13 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0
   replace(z, z', z'') -{ 24 + 9*m'' + 2*m''*x + m''^2 + 9*x + x^2 }-> s14 :|: s14 >= 0, s14 <= z' + (1 + (1 + m'') + x), m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s15 :|: s15 >= 0, s15 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z - 1 >= 0, z' >= 0
   replace(z, z', z'') -{ 27 + 10*m1 + 2*m1*x + m1^2 + 9*x + x^2 }-> s16 :|: s16 >= 0, s16 <= z' + (1 + (1 + m1) + x), s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
   sort(z) -{ 1 }-> 0 :|: z = 0
   sort(z) -{ 135 + 72*m2 + 18*m2*n + 20*m2*x' + 10*m2^2 + 64*n + 18*n*x' + 9*n^2 + 71*x' + 10*x'^2 }-> 1 + s10 + sort(s20) :|: s20 >= 0, s20 <= n + (1 + m2 + x'), s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
   sort(z) -{ 17 + 6*n + 2*n*x + n^2 + 11*x + 2*x^2 }-> 1 + s12 + sort(s21) :|: s21 >= 0, s21 <= n + x, s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
   sort(z) -{ 18 }-> 1 + s8 + sort(s18) :|: s18 >= 0, s18 <= 0 + 0, s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
   sort(z) -{ 13 + 4*z + z^2 }-> 1 + s9 + sort(s19) :|: s19 >= 0, s19 <= 1 + (z - 2) + 0, s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0

Function symbols to be analyzed: 
Previous analysis results are:
  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]
  sort: runtime: O(n^3) [1 + 183*z + 228*z^2 + 91*z^3], size: O(n^2) [z + z^2]

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

(45) FinalProof (FINISHED)
Computed overall runtime complexity
----------------------------------------

(46)
BOUNDS(1, n^3)

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

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

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


The TRS R consists of the following rules:

   eq(0', 0') -> true
   eq(0', s(m)) -> false
   eq(s(n), 0') -> false
   eq(s(n), s(m)) -> eq(n, m)
   le(0', m) -> true
   le(s(n), 0') -> false
   le(s(n), s(m)) -> le(n, m)
   min(cons(0', nil)) -> 0'
   min(cons(s(n), nil)) -> s(n)
   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
   replace(n, m, nil) -> nil
   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
   if_replace(true, n, m, cons(k, x)) -> cons(m, x)
   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
   sort(nil) -> nil
   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

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

(50)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(m)) -> false
eq(s(n), 0') -> false
eq(s(n), s(m)) -> eq(n, m)
le(0', m) -> true
le(s(n), 0') -> false
le(s(n), s(m)) -> le(n, m)
min(cons(0', nil)) -> 0'
min(cons(s(n), nil)) -> s(n)
min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
replace(n, m, nil) -> nil
replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
if_replace(true, n, m, cons(k, x)) -> cons(m, x)
if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
sort(nil) -> nil
sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons

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

(51) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
eq, le, min, replace, sort

They will be analysed ascendingly in the following order:
eq < replace
le < min
min < sort
replace < sort

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

(52)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(m)) -> false
eq(s(n), 0') -> false
eq(s(n), s(m)) -> eq(n, m)
le(0', m) -> true
le(s(n), 0') -> false
le(s(n), s(m)) -> le(n, m)
min(cons(0', nil)) -> 0'
min(cons(s(n), nil)) -> s(n)
min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
replace(n, m, nil) -> nil
replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
if_replace(true, n, m, cons(k, x)) -> cons(m, x)
if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
sort(nil) -> nil
sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Generator Equations:
gen_0':s4_0(0) <=> 0'
gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
gen_nil:cons5_0(0) <=> nil
gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))


The following defined symbols remain to be analysed:
eq, le, min, replace, sort

They will be analysed ascendingly in the following order:
eq < replace
le < min
min < sort
replace < sort

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

(53) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)

Induction Base:
eq(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1)
true

Induction Step:
eq(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1)
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH
true

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

(54)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(m)) -> false
eq(s(n), 0') -> false
eq(s(n), s(m)) -> eq(n, m)
le(0', m) -> true
le(s(n), 0') -> false
le(s(n), s(m)) -> le(n, m)
min(cons(0', nil)) -> 0'
min(cons(s(n), nil)) -> s(n)
min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
replace(n, m, nil) -> nil
replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
if_replace(true, n, m, cons(k, x)) -> cons(m, x)
if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
sort(nil) -> nil
sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Generator Equations:
gen_0':s4_0(0) <=> 0'
gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
gen_nil:cons5_0(0) <=> nil
gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))


The following defined symbols remain to be analysed:
eq, le, min, replace, sort

They will be analysed ascendingly in the following order:
eq < replace
le < min
min < sort
replace < sort

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

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

(57)
BOUNDS(n^1, INF)

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

(58)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(m)) -> false
eq(s(n), 0') -> false
eq(s(n), s(m)) -> eq(n, m)
le(0', m) -> true
le(s(n), 0') -> false
le(s(n), s(m)) -> le(n, m)
min(cons(0', nil)) -> 0'
min(cons(s(n), nil)) -> s(n)
min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
replace(n, m, nil) -> nil
replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
if_replace(true, n, m, cons(k, x)) -> cons(m, x)
if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
sort(nil) -> nil
sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)


Generator Equations:
gen_0':s4_0(0) <=> 0'
gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
gen_nil:cons5_0(0) <=> nil
gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))


The following defined symbols remain to be analysed:
le, min, replace, sort

They will be analysed ascendingly in the following order:
le < min
min < sort
replace < sort

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

(59) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)

Induction Base:
le(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1)
true

Induction Step:
le(gen_0':s4_0(+(n548_0, 1)), gen_0':s4_0(+(n548_0, 1))) ->_R^Omega(1)
le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) ->_IH
true

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

(60)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(m)) -> false
eq(s(n), 0') -> false
eq(s(n), s(m)) -> eq(n, m)
le(0', m) -> true
le(s(n), 0') -> false
le(s(n), s(m)) -> le(n, m)
min(cons(0', nil)) -> 0'
min(cons(s(n), nil)) -> s(n)
min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
replace(n, m, nil) -> nil
replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
if_replace(true, n, m, cons(k, x)) -> cons(m, x)
if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
sort(nil) -> nil
sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)


Generator Equations:
gen_0':s4_0(0) <=> 0'
gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
gen_nil:cons5_0(0) <=> nil
gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))


The following defined symbols remain to be analysed:
min, replace, sort

They will be analysed ascendingly in the following order:
min < sort
replace < sort

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

(61) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
min(gen_nil:cons5_0(+(1, n883_0))) -> gen_0':s4_0(0), rt in Omega(1 + n883_0)

Induction Base:
min(gen_nil:cons5_0(+(1, 0))) ->_R^Omega(1)
0'

Induction Step:
min(gen_nil:cons5_0(+(1, +(n883_0, 1)))) ->_R^Omega(1)
if_min(le(0', 0'), cons(0', cons(0', gen_nil:cons5_0(n883_0)))) ->_L^Omega(1)
if_min(true, cons(0', cons(0', gen_nil:cons5_0(n883_0)))) ->_R^Omega(1)
min(cons(0', gen_nil:cons5_0(n883_0))) ->_IH
gen_0':s4_0(0)

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

(62)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(m)) -> false
eq(s(n), 0') -> false
eq(s(n), s(m)) -> eq(n, m)
le(0', m) -> true
le(s(n), 0') -> false
le(s(n), s(m)) -> le(n, m)
min(cons(0', nil)) -> 0'
min(cons(s(n), nil)) -> s(n)
min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
replace(n, m, nil) -> nil
replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
if_replace(true, n, m, cons(k, x)) -> cons(m, x)
if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
sort(nil) -> nil
sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)
min(gen_nil:cons5_0(+(1, n883_0))) -> gen_0':s4_0(0), rt in Omega(1 + n883_0)


Generator Equations:
gen_0':s4_0(0) <=> 0'
gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
gen_nil:cons5_0(0) <=> nil
gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))


The following defined symbols remain to be analysed:
replace, sort

They will be analysed ascendingly in the following order:
replace < sort

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

(63) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
sort(gen_nil:cons5_0(+(1, n1604_0))) -> *6_0, rt in Omega(n1604_0 + n1604_0^2)

Induction Base:
sort(gen_nil:cons5_0(+(1, 0)))

Induction Step:
sort(gen_nil:cons5_0(+(1, +(n1604_0, 1)))) ->_R^Omega(1)
cons(min(cons(0', gen_nil:cons5_0(+(1, n1604_0)))), sort(replace(min(cons(0', gen_nil:cons5_0(+(1, n1604_0)))), 0', gen_nil:cons5_0(+(1, n1604_0))))) ->_L^Omega(2 + n1604_0)
cons(gen_0':s4_0(0), sort(replace(min(cons(0', gen_nil:cons5_0(+(1, n1604_0)))), 0', gen_nil:cons5_0(+(1, n1604_0))))) ->_L^Omega(2 + n1604_0)
cons(gen_0':s4_0(0), sort(replace(gen_0':s4_0(0), 0', gen_nil:cons5_0(+(1, n1604_0))))) ->_R^Omega(1)
cons(gen_0':s4_0(0), sort(if_replace(eq(gen_0':s4_0(0), 0'), gen_0':s4_0(0), 0', cons(0', gen_nil:cons5_0(n1604_0))))) ->_L^Omega(1)
cons(gen_0':s4_0(0), sort(if_replace(true, gen_0':s4_0(0), 0', cons(0', gen_nil:cons5_0(n1604_0))))) ->_R^Omega(1)
cons(gen_0':s4_0(0), sort(cons(0', gen_nil:cons5_0(n1604_0)))) ->_IH
cons(gen_0':s4_0(0), *6_0)

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

(64)
Obligation:
Proved the lower bound n^2 for the following obligation:

Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(m)) -> false
eq(s(n), 0') -> false
eq(s(n), s(m)) -> eq(n, m)
le(0', m) -> true
le(s(n), 0') -> false
le(s(n), s(m)) -> le(n, m)
min(cons(0', nil)) -> 0'
min(cons(s(n), nil)) -> s(n)
min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
replace(n, m, nil) -> nil
replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
if_replace(true, n, m, cons(k, x)) -> cons(m, x)
if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
sort(nil) -> nil
sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
if_min :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
sort :: nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)
min(gen_nil:cons5_0(+(1, n883_0))) -> gen_0':s4_0(0), rt in Omega(1 + n883_0)


Generator Equations:
gen_0':s4_0(0) <=> 0'
gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
gen_nil:cons5_0(0) <=> nil
gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))


The following defined symbols remain to be analysed:
sort
----------------------------------------

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

(66)
BOUNDS(n^2, INF)