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


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


WORST_CASE(Omega(n^1), O(n^2))
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, n^2).

(0) CpxRelTRS
(1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 378 ms]
(2) CpxRelTRS
(3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CpxWeightedTrs
    (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxWeightedTrs
    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxTypedWeightedTrs
    (9) CompletionProof [UPPER BOUND(ID), 0 ms]
    (10) CpxTypedWeightedCompleteTrs
    (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CpxTypedWeightedCompleteTrs
    (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 6 ms]
    (14) CpxRNTS
    (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) CpxRNTS
    (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) CpxRNTS
    (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (20) CpxRNTS
    (21) IntTrsBoundProof [UPPER BOUND(ID), 157 ms]
    (22) CpxRNTS
    (23) IntTrsBoundProof [UPPER BOUND(ID), 58 ms]
    (24) CpxRNTS
    (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (26) CpxRNTS
    (27) IntTrsBoundProof [UPPER BOUND(ID), 443 ms]
    (28) CpxRNTS
    (29) IntTrsBoundProof [UPPER BOUND(ID), 86 ms]
    (30) CpxRNTS
    (31) ResultPropagationProof [UPPER BOUND(ID), 1 ms]
    (32) CpxRNTS
    (33) IntTrsBoundProof [UPPER BOUND(ID), 431 ms]
    (34) CpxRNTS
    (35) IntTrsBoundProof [UPPER BOUND(ID), 125 ms]
    (36) CpxRNTS
    (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (38) CpxRNTS
    (39) IntTrsBoundProof [UPPER BOUND(ID), 270 ms]
    (40) CpxRNTS
    (41) IntTrsBoundProof [UPPER BOUND(ID), 104 ms]
    (42) CpxRNTS
    (43) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (44) CpxRNTS
    (45) IntTrsBoundProof [UPPER BOUND(ID), 3077 ms]
    (46) CpxRNTS
    (47) IntTrsBoundProof [UPPER BOUND(ID), 1349 ms]
    (48) CpxRNTS
    (49) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (50) CpxRNTS
    (51) IntTrsBoundProof [UPPER BOUND(ID), 652 ms]
    (52) CpxRNTS
    (53) IntTrsBoundProof [UPPER BOUND(ID), 276 ms]
    (54) CpxRNTS
    (55) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (56) CpxRNTS
    (57) IntTrsBoundProof [UPPER BOUND(ID), 249 ms]
    (58) CpxRNTS
    (59) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (60) CpxRNTS
    (61) FinalProof [FINISHED, 0 ms]
    (62) BOUNDS(1, n^2)
(63) RenamingProof [BOTH BOUNDS(ID, ID), 2 ms]
(64) CpxRelTRS
    (65) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (66) typed CpxTrs
    (67) OrderProof [LOWER BOUND(ID), 0 ms]
    (68) typed CpxTrs
    (69) RewriteLemmaProof [LOWER BOUND(ID), 287 ms]
    (70) BEST
        (71) proven lower bound
            (72) LowerBoundPropagationProof [FINISHED, 0 ms]
            (73) BOUNDS(n^1, INF)
        (74) typed CpxTrs
            (75) RewriteLemmaProof [LOWER BOUND(ID), 42 ms]
            (76) typed CpxTrs
            (77) RewriteLemmaProof [LOWER BOUND(ID), 14 ms]
            (78) typed CpxTrs
            (79) RewriteLemmaProof [LOWER BOUND(ID), 70 ms]
            (80) typed CpxTrs


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

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


The TRS R consists of the following rules:

   qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
   quicksort(Cons(x, Nil)) -> Cons(x, Nil)
   quicksort(Nil) -> Nil
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
   part(x, Nil, xs1, xs2) -> app(xs1, xs2)
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
   app(Nil, ys) -> ys
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False

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

   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   >(S(x), S(y)) -> >(x, y)
   >(0, y) -> False
   >(S(x), 0) -> True
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

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, n^2).


The TRS R consists of the following rules:

   qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
   quicksort(Cons(x, Nil)) -> Cons(x, Nil)
   quicksort(Nil) -> Nil
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
   part(x, Nil, xs1, xs2) -> app(xs1, xs2)
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
   app(Nil, ys) -> ys
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False

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

   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   >(S(x), S(y)) -> >(x, y)
   >(0, y) -> False
   >(S(x), 0) -> True
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

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

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

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


The TRS R consists of the following rules:

   qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1]
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1]
   quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1]
   quicksort(Nil) -> Nil [1]
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) [1]
   part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1]
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
   app(Nil, ys) -> ys [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   <(S(x), S(y)) -> <(x, y) [0]
   <(0, S(y)) -> True [0]
   <(x, 0) -> False [0]
   >(S(x), S(y)) -> >(x, y) [0]
   >(0, y) -> False [0]
   >(S(x), 0) -> True [0]
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0]
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0]
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) [0]
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0]

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

(5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
Renamed defined symbols to avoid conflicts with arithmetic symbols:

> => gr
< => lt

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

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


The TRS R consists of the following rules:

   qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1]
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1]
   quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1]
   quicksort(Nil) -> Nil [1]
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](gr(x', x), x', Cons(x, xs), xs1, xs2) [1]
   part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1]
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
   app(Nil, ys) -> ys [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   lt(S(x), S(y)) -> lt(x, y) [0]
   lt(0, S(y)) -> True [0]
   lt(x, 0) -> False [0]
   gr(S(x), S(y)) -> gr(x, y) [0]
   gr(0, y) -> False [0]
   gr(S(x), 0) -> True [0]
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0]
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0]
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](lt(x', x), x', Cons(x, xs), xs1, xs2) [0]
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0]

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

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

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

   qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1]
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1]
   quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1]
   quicksort(Nil) -> Nil [1]
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](gr(x', x), x', Cons(x, xs), xs1, xs2) [1]
   part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1]
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
   app(Nil, ys) -> ys [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   lt(S(x), S(y)) -> lt(x, y) [0]
   lt(0, S(y)) -> True [0]
   lt(x, 0) -> False [0]
   gr(S(x), S(y)) -> gr(x, y) [0]
   gr(0, y) -> False [0]
   gr(S(x), 0) -> True [0]
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0]
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0]
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](lt(x', x), x', Cons(x, xs), xs1, xs2) [0]
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0]

The TRS has the following type information:
qs :: S:0 -> Cons:Nil -> Cons:Nil
Cons :: S:0 -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
gr :: S:0 -> S:0 -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
lt :: S:0 -> S:0 -> True:False
S :: S:0 -> S:0
0 :: S:0
part[False][Ite] :: True:False -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil

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

(9) 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:

   notEmpty_1

(c) The following functions are completely defined:

   quicksort_1
   part_4
   app_2
   qs_2
   lt_2
   gr_2
   part[Ite]_5
   part[False][Ite]_5

Due to the following rules being added:

   lt(v0, v1) -> null_lt [0]
   gr(v0, v1) -> null_gr [0]
   part[Ite](v0, v1, v2, v3, v4) -> Nil [0]
   part[False][Ite](v0, v1, v2, v3, v4) -> Nil [0]
   qs(v0, v1) -> Nil [0]

And the following fresh constants:    null_lt, null_gr

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

(10)
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:

   qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1]
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1]
   quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1]
   quicksort(Nil) -> Nil [1]
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](gr(x', x), x', Cons(x, xs), xs1, xs2) [1]
   part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1]
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
   app(Nil, ys) -> ys [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   lt(S(x), S(y)) -> lt(x, y) [0]
   lt(0, S(y)) -> True [0]
   lt(x, 0) -> False [0]
   gr(S(x), S(y)) -> gr(x, y) [0]
   gr(0, y) -> False [0]
   gr(S(x), 0) -> True [0]
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0]
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0]
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](lt(x', x), x', Cons(x, xs), xs1, xs2) [0]
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0]
   lt(v0, v1) -> null_lt [0]
   gr(v0, v1) -> null_gr [0]
   part[Ite](v0, v1, v2, v3, v4) -> Nil [0]
   part[False][Ite](v0, v1, v2, v3, v4) -> Nil [0]
   qs(v0, v1) -> Nil [0]

The TRS has the following type information:
qs :: S:0 -> Cons:Nil -> Cons:Nil
Cons :: S:0 -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
gr :: S:0 -> S:0 -> True:False:null_lt:null_gr
notEmpty :: Cons:Nil -> True:False:null_lt:null_gr
True :: True:False:null_lt:null_gr
False :: True:False:null_lt:null_gr
lt :: S:0 -> S:0 -> True:False:null_lt:null_gr
S :: S:0 -> S:0
0 :: S:0
part[False][Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
null_lt :: True:False:null_lt:null_gr
null_gr :: True:False:null_lt:null_gr

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

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

(12)
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:

   qs(x', Cons(x, Cons(x'', Cons(x''', xs')))) -> app(Cons(x, Nil), Cons(x', qs(x'', part(x'', Cons(x''', xs'), Nil, Nil)))) [2]
   qs(x', Cons(x, Cons(x1, Nil))) -> app(Cons(x, Nil), Cons(x', Cons(x1, Nil))) [2]
   qs(x', Cons(x, Nil)) -> app(Cons(x, Nil), Cons(x', Nil)) [2]
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part[Ite](gr(x, x'), x, Cons(x', xs), Nil, Nil)) [2]
   quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1]
   quicksort(Nil) -> Nil [1]
   part(S(x2), Cons(S(y'), xs), xs1, xs2) -> part[Ite](gr(x2, y'), S(x2), Cons(S(y'), xs), xs1, xs2) [1]
   part(0, Cons(x, xs), xs1, xs2) -> part[Ite](False, 0, Cons(x, xs), xs1, xs2) [1]
   part(S(x3), Cons(0, xs), xs1, xs2) -> part[Ite](True, S(x3), Cons(0, xs), xs1, xs2) [1]
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](null_gr, x', Cons(x, xs), xs1, xs2) [1]
   part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1]
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
   app(Nil, ys) -> ys [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   lt(S(x), S(y)) -> lt(x, y) [0]
   lt(0, S(y)) -> True [0]
   lt(x, 0) -> False [0]
   gr(S(x), S(y)) -> gr(x, y) [0]
   gr(0, y) -> False [0]
   gr(S(x), 0) -> True [0]
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0]
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0]
   part[Ite](False, S(x4), Cons(S(y''), xs), xs1, xs2) -> part[False][Ite](lt(x4, y''), S(x4), Cons(S(y''), xs), xs1, xs2) [0]
   part[Ite](False, 0, Cons(S(y1), xs), xs1, xs2) -> part[False][Ite](True, 0, Cons(S(y1), xs), xs1, xs2) [0]
   part[Ite](False, x', Cons(0, xs), xs1, xs2) -> part[False][Ite](False, x', Cons(0, xs), xs1, xs2) [0]
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](null_lt, x', Cons(x, xs), xs1, xs2) [0]
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0]
   lt(v0, v1) -> null_lt [0]
   gr(v0, v1) -> null_gr [0]
   part[Ite](v0, v1, v2, v3, v4) -> Nil [0]
   part[False][Ite](v0, v1, v2, v3, v4) -> Nil [0]
   qs(v0, v1) -> Nil [0]

The TRS has the following type information:
qs :: S:0 -> Cons:Nil -> Cons:Nil
Cons :: S:0 -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
gr :: S:0 -> S:0 -> True:False:null_lt:null_gr
notEmpty :: Cons:Nil -> True:False:null_lt:null_gr
True :: True:False:null_lt:null_gr
False :: True:False:null_lt:null_gr
lt :: S:0 -> S:0 -> True:False:null_lt:null_gr
S :: S:0 -> S:0
0 :: S:0
part[False][Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
null_lt :: True:False:null_lt:null_gr
null_gr :: True:False:null_lt:null_gr

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

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

   Nil => 0
   True => 2
   False => 1
   0 => 0
   null_lt => 0
   null_gr => 0

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

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

   app(z, z') -{ 1 }-> ys :|: z' = ys, ys >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, ys) :|: z = 1 + x + xs, xs >= 0, z' = ys, ys >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   gr(z, z') -{ 0 }-> 2 :|: x >= 0, z = 1 + x, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: y >= 0, z = 0, z' = y
   gr(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   lt(z, z') -{ 0 }-> lt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
   lt(z, z') -{ 0 }-> 2 :|: z' = 1 + y, y >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: x >= 0, z = x, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(x2, y'), 1 + x2, 1 + (1 + y') + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + (1 + y') + xs, z1 = xs2, z = 1 + x2, y' >= 0, z'' = xs1, xs1 >= 0, x2 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + x3, 1 + 0 + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + 0 + xs, z1 = xs2, z'' = xs1, xs1 >= 0, z = 1 + x3, x3 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + x + xs, z1 = xs2, x >= 0, z'' = xs1, xs1 >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, x', 1 + x + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + x + xs, z1 = xs2, x' >= 0, x >= 0, z'' = xs1, xs1 >= 0, z = x'
   part(z, z', z'', z1) -{ 1 }-> app(xs1, xs2) :|: xs2 >= 0, z1 = xs2, x >= 0, z'' = xs1, xs1 >= 0, z = x, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(x', xs, xs1, xs2) :|: z' = x', xs >= 0, xs2 >= 0, z = 1, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(x', xs, xs1, 1 + x + xs2) :|: z = 2, z' = x', xs >= 0, xs2 >= 0, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(x4, y''), 1 + x4, 1 + (1 + y'') + xs, xs1, xs2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, x4 >= 0, xs2 >= 0, z = 1, z2 = xs2, z' = 1 + x4, y'' >= 0, z1 = xs1, xs1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, xs1, xs2) :|: y1 >= 0, xs >= 0, xs2 >= 0, z = 1, z2 = xs2, z'' = 1 + (1 + y1) + xs, z1 = xs1, xs1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, x', 1 + 0 + xs, xs1, xs2) :|: z' = x', xs >= 0, xs2 >= 0, z'' = 1 + 0 + xs, z = 1, z2 = xs2, x' >= 0, z1 = xs1, xs1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, x', 1 + x + xs, xs1, xs2) :|: z' = x', xs >= 0, xs2 >= 0, z = 1, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(x', xs, 1 + x + xs1, xs2) :|: z = 2, z' = x', xs >= 0, xs2 >= 0, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + x' + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: x' >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0, z = x'
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + x' + 0) :|: x' >= 0, x >= 0, z' = 1 + x + 0, z = x'
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + x' + (1 + x1 + 0)) :|: x1 >= 0, x' >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0), z = x'
   qs(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + x + 0 :|: x >= 0, z = 1 + x + 0


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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0


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

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

   { notEmpty }
   { gr }
   { lt }
   { app }
   { part, part[False][Ite], part[Ite] }
   { qs }
   { quicksort }

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {notEmpty}, {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {notEmpty}, {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}

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

(21) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {notEmpty}, {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: ?, size: O(1) [2]

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

(23) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: notEmpty
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:

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]

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

(27) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: ?, size: O(1) [2]

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

(29) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]

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

(33) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: ?, size: O(1) [2]

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

(35) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]

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

(39) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: ?, size: O(n^1) [z + z']

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

(41) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']

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

(45) IntTrsBoundProof (UPPER BOUND(ID))

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

Computed SIZE bound using KoAT for: part[False][Ite]
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z'' + z1 + z2

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {part,part[False][Ite],part[Ite]}, {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: ?, size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: ?, size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: ?, size: O(n^1) [z'' + z1 + z2]

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

(47) IntTrsBoundProof (UPPER BOUND(ID))

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

Computed RUNTIME bound using CoFloCo for: part[False][Ite]
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 2*z'' + z1

Computed RUNTIME bound using CoFloCo for: part[Ite]
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 1 + 2*z'' + z1

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2]

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 6 + 2*x''' + 2*xs' }-> app(1 + x + 0, 1 + z + qs(x'', s7)) :|: s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 5 + 2*x' + 2*xs }-> qs(x, s8) :|: s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2]

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

(51) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 6 + 2*x''' + 2*xs' }-> app(1 + x + 0, 1 + z + qs(x'', s7)) :|: s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 5 + 2*x' + 2*xs }-> qs(x, s8) :|: s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {qs}, {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  qs: runtime: ?, size: O(n^1) [1 + z + z']

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

(53) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 6 + 2*x''' + 2*xs' }-> app(1 + x + 0, 1 + z + qs(x'', s7)) :|: s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 5 + 2*x' + 2*xs }-> qs(x, s8) :|: s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z']

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 14 + 8*s7 + 2*s7^2 + x + 2*x''' + 2*xs' }-> s21 :|: s20 >= 0, s20 <= x'' + s7 + 1, s21 >= 0, s21 <= 1 + x + 0 + (1 + z + s20), s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 11 + 8*s8 + 2*s8^2 + 2*x' + 2*xs }-> s22 :|: s22 >= 0, s22 <= x + s8 + 1, s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z']

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

(57) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 14 + 8*s7 + 2*s7^2 + x + 2*x''' + 2*xs' }-> s21 :|: s20 >= 0, s20 <= x'' + s7 + 1, s21 >= 0, s21 <= 1 + x + 0 + (1 + z + s20), s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 11 + 8*s8 + 2*s8^2 + 2*x' + 2*xs }-> s22 :|: s22 >= 0, s22 <= x + s8 + 1, s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: {quicksort}
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z']
  quicksort: runtime: ?, size: O(n^1) [z]

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

(59) IntTrsBoundProof (UPPER BOUND(ID))

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

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

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

   app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
   app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0
   gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0
   gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0
   gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0
   gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0
   lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0
   lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0
   lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0
   part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0
   part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0
   part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0
   part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0
   part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0
   part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs
   part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0
   qs(z, z') -{ 14 + 8*s7 + 2*s7^2 + x + 2*x''' + 2*xs' }-> s21 :|: s20 >= 0, s20 <= x'' + s7 + 1, s21 >= 0, s21 <= 1 + x + 0 + (1 + z + s20), s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0
   qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0)
   qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0
   qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   quicksort(z) -{ 11 + 8*s8 + 2*s8^2 + 2*x' + 2*xs }-> s22 :|: s22 >= 0, s22 <= x + s8 + 1, s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs)
   quicksort(z) -{ 1 }-> 0 :|: z = 0
   quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0

Function symbols to be analyzed: 
Previous analysis results are:
  notEmpty: runtime: O(1) [1], size: O(1) [2]
  gr: runtime: O(1) [0], size: O(1) [2]
  lt: runtime: O(1) [0], size: O(1) [2]
  app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
  part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1]
  part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2]
  qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z']
  quicksort: runtime: O(n^2) [23 + 28*z + 8*z^2], size: O(n^1) [z]

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

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

(62)
BOUNDS(1, n^2)

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

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

(64)
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:

   qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
   quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
   quicksort(Cons(x, Nil)) -> Cons(x, Nil)
   quicksort(Nil) -> Nil
   part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
   part(x, Nil, xs1, xs2) -> app(xs1, xs2)
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
   app(Nil, ys) -> ys
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False

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

   <(S(x), S(y)) -> <(x, y)
   <(0', S(y)) -> True
   <(x, 0') -> False
   >(S(x), S(y)) -> >(x, y)
   >(0', y) -> False
   >(S(x), 0') -> True
   part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
   part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
   part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
   part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

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

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

(66)
Obligation:
Innermost TRS:
Rules:
qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
part(x, Nil, xs1, xs2) -> app(xs1, xs2)
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
>(S(x), S(y)) -> >(x, y)
>(0', y) -> False
>(S(x), 0') -> True
part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

Types:
qs :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
< :: S:0' -> S:0' -> True:False
S :: S:0' -> S:0'
0' :: S:0'
part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'

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

(67) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
app, quicksort, part, >, <

They will be analysed ascendingly in the following order:
app < quicksort
app < part
part < quicksort
> < part
< < part

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

(68)
Obligation:
Innermost TRS:
Rules:
qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
part(x, Nil, xs1, xs2) -> app(xs1, xs2)
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
>(S(x), S(y)) -> >(x, y)
>(0', y) -> False
>(S(x), 0') -> True
part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

Types:
qs :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
< :: S:0' -> S:0' -> True:False
S :: S:0' -> S:0'
0' :: S:0'
part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
app, quicksort, part, >, <

They will be analysed ascendingly in the following order:
app < quicksort
app < part
part < quicksort
> < part
< < part

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

(69) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0)

Induction Base:
app(gen_Cons:Nil4_0(0), gen_Cons:Nil4_0(b)) ->_R^Omega(1)
gen_Cons:Nil4_0(b)

Induction Step:
app(gen_Cons:Nil4_0(+(n7_0, 1)), gen_Cons:Nil4_0(b)) ->_R^Omega(1)
Cons(0', app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b))) ->_IH
Cons(0', gen_Cons:Nil4_0(+(b, c8_0)))

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

(70)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
part(x, Nil, xs1, xs2) -> app(xs1, xs2)
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
>(S(x), S(y)) -> >(x, y)
>(0', y) -> False
>(S(x), 0') -> True
part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

Types:
qs :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
< :: S:0' -> S:0' -> True:False
S :: S:0' -> S:0'
0' :: S:0'
part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
app, quicksort, part, >, <

They will be analysed ascendingly in the following order:
app < quicksort
app < part
part < quicksort
> < part
< < part

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

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

(73)
BOUNDS(n^1, INF)

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

(74)
Obligation:
Innermost TRS:
Rules:
qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
part(x, Nil, xs1, xs2) -> app(xs1, xs2)
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
>(S(x), S(y)) -> >(x, y)
>(0', y) -> False
>(S(x), 0') -> True
part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

Types:
qs :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
< :: S:0' -> S:0' -> True:False
S :: S:0' -> S:0'
0' :: S:0'
part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
>, quicksort, part, <

They will be analysed ascendingly in the following order:
part < quicksort
> < part
< < part

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

(75) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
>(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0)

Induction Base:
>(gen_S:0'5_0(0), gen_S:0'5_0(0)) ->_R^Omega(0)
False

Induction Step:
>(gen_S:0'5_0(+(n892_0, 1)), gen_S:0'5_0(+(n892_0, 1))) ->_R^Omega(0)
>(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) ->_IH
False

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

(76)
Obligation:
Innermost TRS:
Rules:
qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
part(x, Nil, xs1, xs2) -> app(xs1, xs2)
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
>(S(x), S(y)) -> >(x, y)
>(0', y) -> False
>(S(x), 0') -> True
part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

Types:
qs :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
< :: S:0' -> S:0' -> True:False
S :: S:0' -> S:0'
0' :: S:0'
part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0)
>(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
<, quicksort, part

They will be analysed ascendingly in the following order:
part < quicksort
< < part

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

(77) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
<(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) -> True, rt in Omega(0)

Induction Base:
<(gen_S:0'5_0(0), gen_S:0'5_0(+(1, 0))) ->_R^Omega(0)
True

Induction Step:
<(gen_S:0'5_0(+(n1173_0, 1)), gen_S:0'5_0(+(1, +(n1173_0, 1)))) ->_R^Omega(0)
<(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) ->_IH
True

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

(78)
Obligation:
Innermost TRS:
Rules:
qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
part(x, Nil, xs1, xs2) -> app(xs1, xs2)
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
>(S(x), S(y)) -> >(x, y)
>(0', y) -> False
>(S(x), 0') -> True
part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

Types:
qs :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
< :: S:0' -> S:0' -> True:False
S :: S:0' -> S:0'
0' :: S:0'
part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0)
>(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0)
<(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) -> True, rt in Omega(0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
part, quicksort

They will be analysed ascendingly in the following order:
part < quicksort

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

(79) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
part(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1459_0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) -> gen_Cons:Nil4_0(+(c, d)), rt in Omega(1 + c + n1459_0)

Induction Base:
part(gen_S:0'5_0(0), gen_Cons:Nil4_0(0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(1)
app(gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_L^Omega(1 + c)
gen_Cons:Nil4_0(+(c, d))

Induction Step:
part(gen_S:0'5_0(0), gen_Cons:Nil4_0(+(n1459_0, 1)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(1)
part[Ite](>(gen_S:0'5_0(0), 0'), gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_L^Omega(0)
part[Ite](False, gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(0)
part[False][Ite](<(gen_S:0'5_0(0), 0'), gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(0)
part[False][Ite](False, gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(0)
part(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1459_0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_IH
gen_Cons:Nil4_0(+(c, d))

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

(80)
Obligation:
Innermost TRS:
Rules:
qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs)))
quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2)
part(x, Nil, xs1, xs2) -> app(xs1, xs2)
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
>(S(x), S(y)) -> >(x, y)
>(0', y) -> False
>(S(x), 0') -> True
part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2)
part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2))
part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2)
part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2)

Types:
qs :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
quicksort :: Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
< :: S:0' -> S:0' -> True:False
S :: S:0' -> S:0'
0' :: S:0'
part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0)
>(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0)
<(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) -> True, rt in Omega(0)
part(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1459_0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) -> gen_Cons:Nil4_0(+(c, d)), rt in Omega(1 + c + n1459_0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
quicksort