WORST_CASE(Omega(n^2),?)
proof of input_eS4RegZxLy.trs
# AProVE Commit ID: aff8ecad908e01718a4c36e68d2e55d5e0f16e15 fuhs 20220216 unpublished


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

(0) CpxTRS
(1) CpxTrsToCdtProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CdtProblem
(3) CdtToCpxRelTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CpxRelTRS
(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
(7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(8) typed CpxTrs
(9) OrderProof [LOWER BOUND(ID), 0 ms]
(10) typed CpxTrs
(11) RewriteLemmaProof [LOWER BOUND(ID), 359 ms]
(12) BEST
    (13) proven lower bound
        (14) LowerBoundPropagationProof [FINISHED, 0 ms]
        (15) BOUNDS(n^1, INF)
    (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 17 ms]
        (18) typed CpxTrs
        (19) RewriteLemmaProof [LOWER BOUND(ID), 54 ms]
        (20) typed CpxTrs
        (21) RewriteLemmaProof [LOWER BOUND(ID), 690 ms]
        (22) typed CpxTrs
        (23) RewriteLemmaProof [LOWER BOUND(ID), 662 ms]
        (24) typed CpxTrs
        (25) RewriteLemmaProof [LOWER BOUND(ID), 78 ms]
        (26) typed CpxTrs
        (27) RewriteLemmaProof [LOWER BOUND(ID), 67 ms]
        (28) typed CpxTrs
        (29) RewriteLemmaProof [LOWER BOUND(ID), 74 ms]
        (30) typed CpxTrs
        (31) RewriteLemmaProof [LOWER BOUND(ID), 76 ms]
        (32) typed CpxTrs
        (33) RewriteLemmaProof [LOWER BOUND(ID), 472 ms]
        (34) proven lower bound
        (35) LowerBoundPropagationProof [FINISHED, 0 ms]
        (36) BOUNDS(n^2, INF)


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

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


The TRS R consists of the following rules:

   le(0, Y) -> true
   le(s(X), 0) -> false
   le(s(X), s(Y)) -> le(X, Y)
   app(nil, Y) -> Y
   app(cons(N, L), Y) -> cons(N, app(L, Y))
   low(N, nil) -> nil
   low(N, cons(M, L)) -> iflow(le(M, N), N, cons(M, L))
   iflow(true, N, cons(M, L)) -> cons(M, low(N, L))
   iflow(false, N, cons(M, L)) -> low(N, L)
   high(N, nil) -> nil
   high(N, cons(M, L)) -> ifhigh(le(M, N), N, cons(M, L))
   ifhigh(true, N, cons(M, L)) -> high(N, L)
   ifhigh(false, N, cons(M, L)) -> cons(M, high(N, L))
   quicksort(nil) -> nil
   quicksort(cons(N, L)) -> app(quicksort(low(N, L)), cons(N, quicksort(high(N, L))))

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

(1) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID))
Converted Cpx (relative) TRS with rewrite strategy PARALLEL_INNERMOST to CDT
----------------------------------------

(2)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   le(0, z0) -> true
   le(s(z0), 0) -> false
   le(s(z0), s(z1)) -> le(z0, z1)
   app(nil, z0) -> z0
   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
   low(z0, nil) -> nil
   low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
   iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
   iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
   high(z0, nil) -> nil
   high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
   ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
   ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
   quicksort(nil) -> nil
   quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))
Tuples:
   LE(0, z0) -> c
   LE(s(z0), 0) -> c1
   LE(s(z0), s(z1)) -> c2(LE(z0, z1))
   APP(nil, z0) -> c3
   APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
   LOW(z0, nil) -> c5
   LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
   IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
   HIGH(z0, nil) -> c9
   HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
   IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
   QUICKSORT(nil) -> c13
   QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
   QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
S tuples:
   LE(0, z0) -> c
   LE(s(z0), 0) -> c1
   LE(s(z0), s(z1)) -> c2(LE(z0, z1))
   APP(nil, z0) -> c3
   APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
   LOW(z0, nil) -> c5
   LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
   IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
   HIGH(z0, nil) -> c9
   HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
   IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
   QUICKSORT(nil) -> c13
   QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
   QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
K tuples:none
Defined Rule Symbols:   le_2, app_2, low_2, iflow_3, high_2, ifhigh_3, quicksort_1

Defined Pair Symbols:   LE_2, APP_2, LOW_2, IFLOW_3, HIGH_2, IFHIGH_3, QUICKSORT_1

Compound Symbols:   c, c1, c2_1, c3, c4_1, c5, c6_2, c7_1, c8_1, c9, c10_2, c11_1, c12_1, c13, c14_3, c15_3


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

(3) CdtToCpxRelTrsProof (BOTH BOUNDS(ID, ID))
Converted S to standard rules, and D \ S as well as R to relative rules.
----------------------------------------

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


The TRS R consists of the following rules:

   LE(0, z0) -> c
   LE(s(z0), 0) -> c1
   LE(s(z0), s(z1)) -> c2(LE(z0, z1))
   APP(nil, z0) -> c3
   APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
   LOW(z0, nil) -> c5
   LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
   IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
   HIGH(z0, nil) -> c9
   HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
   IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
   QUICKSORT(nil) -> c13
   QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
   QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))

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

   le(0, z0) -> true
   le(s(z0), 0) -> false
   le(s(z0), s(z1)) -> le(z0, z1)
   app(nil, z0) -> z0
   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
   low(z0, nil) -> nil
   low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
   iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
   iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
   high(z0, nil) -> nil
   high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
   ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
   ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
   quicksort(nil) -> nil
   quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

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

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

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


The TRS R consists of the following rules:

   LE(0', z0) -> c
   LE(s(z0), 0') -> c1
   LE(s(z0), s(z1)) -> c2(LE(z0, z1))
   APP(nil, z0) -> c3
   APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
   LOW(z0, nil) -> c5
   LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
   IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
   HIGH(z0, nil) -> c9
   HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
   IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
   IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
   QUICKSORT(nil) -> c13
   QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
   QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))

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

   le(0', z0) -> true
   le(s(z0), 0') -> false
   le(s(z0), s(z1)) -> le(z0, z1)
   app(nil, z0) -> z0
   app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
   low(z0, nil) -> nil
   low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
   iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
   iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
   high(z0, nil) -> nil
   high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
   ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
   ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
   quicksort(nil) -> nil
   quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

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

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

(8)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15

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

(9) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
LE, APP, LOW, le, HIGH, QUICKSORT, quicksort, low, high, app

They will be analysed ascendingly in the following order:
LE < LOW
LE < HIGH
APP < QUICKSORT
le < LOW
LOW < QUICKSORT
le < HIGH
le < low
le < high
HIGH < QUICKSORT
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

(10)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
LE, APP, LOW, le, HIGH, QUICKSORT, quicksort, low, high, app

They will be analysed ascendingly in the following order:
LE < LOW
LE < HIGH
APP < QUICKSORT
le < LOW
LOW < QUICKSORT
le < HIGH
le < low
le < high
HIGH < QUICKSORT
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

(11) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)

Induction Base:
LE(gen_0':s12_16(0), gen_0':s12_16(0)) ->_R^Omega(1)
c

Induction Step:
LE(gen_0':s12_16(+(n17_16, 1)), gen_0':s12_16(+(n17_16, 1))) ->_R^Omega(1)
c2(LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16))) ->_IH
c2(gen_c:c1:c211_16(c18_16))

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

(12)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
LE, APP, LOW, le, HIGH, QUICKSORT, quicksort, low, high, app

They will be analysed ascendingly in the following order:
LE < LOW
LE < HIGH
APP < QUICKSORT
le < LOW
LOW < QUICKSORT
le < HIGH
le < low
le < high
HIGH < QUICKSORT
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

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

(15)
BOUNDS(n^1, INF)

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

(16)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
APP, LOW, le, HIGH, QUICKSORT, quicksort, low, high, app

They will be analysed ascendingly in the following order:
APP < QUICKSORT
le < LOW
LOW < QUICKSORT
le < HIGH
le < low
le < high
HIGH < QUICKSORT
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)

Induction Base:
APP(gen_nil:cons14_16(0), gen_nil:cons14_16(b)) ->_R^Omega(1)
c3

Induction Step:
APP(gen_nil:cons14_16(+(n650_16, 1)), gen_nil:cons14_16(b)) ->_R^Omega(1)
c4(APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b))) ->_IH
c4(gen_c3:c413_16(c651_16))

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

(18)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
le, LOW, HIGH, QUICKSORT, quicksort, low, high, app

They will be analysed ascendingly in the following order:
le < LOW
LOW < QUICKSORT
le < HIGH
le < low
le < high
HIGH < QUICKSORT
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)

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

Induction Step:
le(gen_0':s12_16(+(n1477_16, 1)), gen_0':s12_16(+(n1477_16, 1))) ->_R^Omega(0)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) ->_IH
true

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

(20)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
LOW, HIGH, QUICKSORT, quicksort, low, high, app

They will be analysed ascendingly in the following order:
LOW < QUICKSORT
HIGH < QUICKSORT
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)

Induction Base:
LOW(gen_0':s12_16(0), gen_nil:cons14_16(0))

Induction Step:
LOW(gen_0':s12_16(0), gen_nil:cons14_16(+(n1878_16, 1))) ->_R^Omega(1)
c6(IFLOW(le(0', gen_0':s12_16(0)), gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n1878_16))), LE(0', gen_0':s12_16(0))) ->_L^Omega(0)
c6(IFLOW(true, gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n1878_16))), LE(0', gen_0':s12_16(0))) ->_R^Omega(1)
c6(c7(LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16))), LE(0', gen_0':s12_16(0))) ->_IH
c6(c7(*16_16), LE(0', gen_0':s12_16(0))) ->_L^Omega(1)
c6(c7(*16_16), gen_c:c1:c211_16(0))

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

(22)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
HIGH, QUICKSORT, quicksort, low, high, app

They will be analysed ascendingly in the following order:
HIGH < QUICKSORT
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16)) -> *16_16, rt in Omega(n7251_16)

Induction Base:
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(0))

Induction Step:
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(+(n7251_16, 1))) ->_R^Omega(1)
c10(IFHIGH(le(0', gen_0':s12_16(0)), gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n7251_16))), LE(0', gen_0':s12_16(0))) ->_L^Omega(0)
c10(IFHIGH(true, gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n7251_16))), LE(0', gen_0':s12_16(0))) ->_R^Omega(1)
c10(c11(HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16))), LE(0', gen_0':s12_16(0))) ->_IH
c10(c11(*16_16), LE(0', gen_0':s12_16(0))) ->_L^Omega(1)
c10(c11(*16_16), gen_c:c1:c211_16(0))

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

(24)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16)) -> *16_16, rt in Omega(n7251_16)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
low, QUICKSORT, quicksort, high, app

They will be analysed ascendingly in the following order:
quicksort < QUICKSORT
low < QUICKSORT
high < QUICKSORT
low < quicksort
high < quicksort
app < quicksort

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

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
low(gen_0':s12_16(0), gen_nil:cons14_16(n15532_16)) -> gen_nil:cons14_16(n15532_16), rt in Omega(0)

Induction Base:
low(gen_0':s12_16(0), gen_nil:cons14_16(0)) ->_R^Omega(0)
nil

Induction Step:
low(gen_0':s12_16(0), gen_nil:cons14_16(+(n15532_16, 1))) ->_R^Omega(0)
iflow(le(0', gen_0':s12_16(0)), gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n15532_16))) ->_L^Omega(0)
iflow(true, gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n15532_16))) ->_R^Omega(0)
cons(0', low(gen_0':s12_16(0), gen_nil:cons14_16(n15532_16))) ->_IH
cons(0', gen_nil:cons14_16(c15533_16))

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

(26)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16)) -> *16_16, rt in Omega(n7251_16)
low(gen_0':s12_16(0), gen_nil:cons14_16(n15532_16)) -> gen_nil:cons14_16(n15532_16), rt in Omega(0)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
high, QUICKSORT, quicksort, app

They will be analysed ascendingly in the following order:
quicksort < QUICKSORT
high < QUICKSORT
high < quicksort
app < quicksort

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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
high(gen_0':s12_16(0), gen_nil:cons14_16(n16816_16)) -> gen_nil:cons14_16(0), rt in Omega(0)

Induction Base:
high(gen_0':s12_16(0), gen_nil:cons14_16(0)) ->_R^Omega(0)
nil

Induction Step:
high(gen_0':s12_16(0), gen_nil:cons14_16(+(n16816_16, 1))) ->_R^Omega(0)
ifhigh(le(0', gen_0':s12_16(0)), gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n16816_16))) ->_L^Omega(0)
ifhigh(true, gen_0':s12_16(0), cons(0', gen_nil:cons14_16(n16816_16))) ->_R^Omega(0)
high(gen_0':s12_16(0), gen_nil:cons14_16(n16816_16)) ->_IH
gen_nil:cons14_16(0)

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

(28)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16)) -> *16_16, rt in Omega(n7251_16)
low(gen_0':s12_16(0), gen_nil:cons14_16(n15532_16)) -> gen_nil:cons14_16(n15532_16), rt in Omega(0)
high(gen_0':s12_16(0), gen_nil:cons14_16(n16816_16)) -> gen_nil:cons14_16(0), rt in Omega(0)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


The following defined symbols remain to be analysed:
app, QUICKSORT, quicksort

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

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

(29) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
app(gen_nil:cons14_16(n18030_16), gen_nil:cons14_16(b)) -> gen_nil:cons14_16(+(n18030_16, b)), rt in Omega(0)

Induction Base:
app(gen_nil:cons14_16(0), gen_nil:cons14_16(b)) ->_R^Omega(0)
gen_nil:cons14_16(b)

Induction Step:
app(gen_nil:cons14_16(+(n18030_16, 1)), gen_nil:cons14_16(b)) ->_R^Omega(0)
cons(0', app(gen_nil:cons14_16(n18030_16), gen_nil:cons14_16(b))) ->_IH
cons(0', gen_nil:cons14_16(+(b, c18031_16)))

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

(30)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16)) -> *16_16, rt in Omega(n7251_16)
low(gen_0':s12_16(0), gen_nil:cons14_16(n15532_16)) -> gen_nil:cons14_16(n15532_16), rt in Omega(0)
high(gen_0':s12_16(0), gen_nil:cons14_16(n16816_16)) -> gen_nil:cons14_16(0), rt in Omega(0)
app(gen_nil:cons14_16(n18030_16), gen_nil:cons14_16(b)) -> gen_nil:cons14_16(+(n18030_16, b)), rt in Omega(0)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


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

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

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

(31) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
quicksort(gen_nil:cons14_16(n20145_16)) -> gen_nil:cons14_16(n20145_16), rt in Omega(0)

Induction Base:
quicksort(gen_nil:cons14_16(0)) ->_R^Omega(0)
nil

Induction Step:
quicksort(gen_nil:cons14_16(+(n20145_16, 1))) ->_R^Omega(0)
app(quicksort(low(0', gen_nil:cons14_16(n20145_16))), cons(0', quicksort(high(0', gen_nil:cons14_16(n20145_16))))) ->_L^Omega(0)
app(quicksort(gen_nil:cons14_16(n20145_16)), cons(0', quicksort(high(0', gen_nil:cons14_16(n20145_16))))) ->_IH
app(gen_nil:cons14_16(c20146_16), cons(0', quicksort(high(0', gen_nil:cons14_16(n20145_16))))) ->_L^Omega(0)
app(gen_nil:cons14_16(n20145_16), cons(0', quicksort(gen_nil:cons14_16(0)))) ->_R^Omega(0)
app(gen_nil:cons14_16(n20145_16), cons(0', nil)) ->_L^Omega(0)
gen_nil:cons14_16(+(n20145_16, +(0, 1)))

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

(32)
Obligation:
Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16)) -> *16_16, rt in Omega(n7251_16)
low(gen_0':s12_16(0), gen_nil:cons14_16(n15532_16)) -> gen_nil:cons14_16(n15532_16), rt in Omega(0)
high(gen_0':s12_16(0), gen_nil:cons14_16(n16816_16)) -> gen_nil:cons14_16(0), rt in Omega(0)
app(gen_nil:cons14_16(n18030_16), gen_nil:cons14_16(b)) -> gen_nil:cons14_16(+(n18030_16, b)), rt in Omega(0)
quicksort(gen_nil:cons14_16(n20145_16)) -> gen_nil:cons14_16(n20145_16), rt in Omega(0)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


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

(33) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
QUICKSORT(gen_nil:cons14_16(n21779_16)) -> *16_16, rt in Omega(n21779_16 + n21779_16^2)

Induction Base:
QUICKSORT(gen_nil:cons14_16(0))

Induction Step:
QUICKSORT(gen_nil:cons14_16(+(n21779_16, 1))) ->_R^Omega(1)
c14(APP(quicksort(low(0', gen_nil:cons14_16(n21779_16))), cons(0', quicksort(high(0', gen_nil:cons14_16(n21779_16))))), QUICKSORT(low(0', gen_nil:cons14_16(n21779_16))), LOW(0', gen_nil:cons14_16(n21779_16))) ->_L^Omega(0)
c14(APP(quicksort(gen_nil:cons14_16(n21779_16)), cons(0', quicksort(high(0', gen_nil:cons14_16(n21779_16))))), QUICKSORT(low(0', gen_nil:cons14_16(n21779_16))), LOW(0', gen_nil:cons14_16(n21779_16))) ->_L^Omega(0)
c14(APP(gen_nil:cons14_16(n21779_16), cons(0', quicksort(high(0', gen_nil:cons14_16(n21779_16))))), QUICKSORT(low(0', gen_nil:cons14_16(n21779_16))), LOW(0', gen_nil:cons14_16(n21779_16))) ->_L^Omega(0)
c14(APP(gen_nil:cons14_16(n21779_16), cons(0', quicksort(gen_nil:cons14_16(0)))), QUICKSORT(low(0', gen_nil:cons14_16(n21779_16))), LOW(0', gen_nil:cons14_16(n21779_16))) ->_L^Omega(0)
c14(APP(gen_nil:cons14_16(n21779_16), cons(0', gen_nil:cons14_16(0))), QUICKSORT(low(0', gen_nil:cons14_16(n21779_16))), LOW(0', gen_nil:cons14_16(n21779_16))) ->_L^Omega(1 + n21779_16)
c14(gen_c3:c413_16(n21779_16), QUICKSORT(low(0', gen_nil:cons14_16(n21779_16))), LOW(0', gen_nil:cons14_16(n21779_16))) ->_L^Omega(0)
c14(gen_c3:c413_16(n21779_16), QUICKSORT(gen_nil:cons14_16(n21779_16)), LOW(0', gen_nil:cons14_16(n21779_16))) ->_IH
c14(gen_c3:c413_16(n21779_16), *16_16, LOW(0', gen_nil:cons14_16(n21779_16))) ->_L^Omega(n21779_16)
c14(gen_c3:c413_16(n21779_16), *16_16, *16_16)

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

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

Innermost TRS:
Rules:
LE(0', z0) -> c
LE(s(z0), 0') -> c1
LE(s(z0), s(z1)) -> c2(LE(z0, z1))
APP(nil, z0) -> c3
APP(cons(z0, z1), z2) -> c4(APP(z1, z2))
LOW(z0, nil) -> c5
LOW(z0, cons(z1, z2)) -> c6(IFLOW(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFLOW(true, z0, cons(z1, z2)) -> c7(LOW(z0, z2))
IFLOW(false, z0, cons(z1, z2)) -> c8(LOW(z0, z2))
HIGH(z0, nil) -> c9
HIGH(z0, cons(z1, z2)) -> c10(IFHIGH(le(z1, z0), z0, cons(z1, z2)), LE(z1, z0))
IFHIGH(true, z0, cons(z1, z2)) -> c11(HIGH(z0, z2))
IFHIGH(false, z0, cons(z1, z2)) -> c12(HIGH(z0, z2))
QUICKSORT(nil) -> c13
QUICKSORT(cons(z0, z1)) -> c14(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(low(z0, z1)), LOW(z0, z1))
QUICKSORT(cons(z0, z1)) -> c15(APP(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1)))), QUICKSORT(high(z0, z1)), HIGH(z0, z1))
le(0', z0) -> true
le(s(z0), 0') -> false
le(s(z0), s(z1)) -> le(z0, z1)
app(nil, z0) -> z0
app(cons(z0, z1), z2) -> cons(z0, app(z1, z2))
low(z0, nil) -> nil
low(z0, cons(z1, z2)) -> iflow(le(z1, z0), z0, cons(z1, z2))
iflow(true, z0, cons(z1, z2)) -> cons(z1, low(z0, z2))
iflow(false, z0, cons(z1, z2)) -> low(z0, z2)
high(z0, nil) -> nil
high(z0, cons(z1, z2)) -> ifhigh(le(z1, z0), z0, cons(z1, z2))
ifhigh(true, z0, cons(z1, z2)) -> high(z0, z2)
ifhigh(false, z0, cons(z1, z2)) -> cons(z1, high(z0, z2))
quicksort(nil) -> nil
quicksort(cons(z0, z1)) -> app(quicksort(low(z0, z1)), cons(z0, quicksort(high(z0, z1))))

Types:
LE :: 0':s -> 0':s -> c:c1:c2
0' :: 0':s
c :: c:c1:c2
s :: 0':s -> 0':s
c1 :: c:c1:c2
c2 :: c:c1:c2 -> c:c1:c2
APP :: nil:cons -> nil:cons -> c3:c4
nil :: nil:cons
c3 :: c3:c4
cons :: 0':s -> nil:cons -> nil:cons
c4 :: c3:c4 -> c3:c4
LOW :: 0':s -> nil:cons -> c5:c6
c5 :: c5:c6
c6 :: c7:c8 -> c:c1:c2 -> c5:c6
IFLOW :: true:false -> 0':s -> nil:cons -> c7:c8
le :: 0':s -> 0':s -> true:false
true :: true:false
c7 :: c5:c6 -> c7:c8
false :: true:false
c8 :: c5:c6 -> c7:c8
HIGH :: 0':s -> nil:cons -> c9:c10
c9 :: c9:c10
c10 :: c11:c12 -> c:c1:c2 -> c9:c10
IFHIGH :: true:false -> 0':s -> nil:cons -> c11:c12
c11 :: c9:c10 -> c11:c12
c12 :: c9:c10 -> c11:c12
QUICKSORT :: nil:cons -> c13:c14:c15
c13 :: c13:c14:c15
c14 :: c3:c4 -> c13:c14:c15 -> c5:c6 -> c13:c14:c15
quicksort :: nil:cons -> nil:cons
low :: 0':s -> nil:cons -> nil:cons
high :: 0':s -> nil:cons -> nil:cons
c15 :: c3:c4 -> c13:c14:c15 -> c9:c10 -> c13:c14:c15
app :: nil:cons -> nil:cons -> nil:cons
iflow :: true:false -> 0':s -> nil:cons -> nil:cons
ifhigh :: true:false -> 0':s -> nil:cons -> nil:cons
hole_c:c1:c21_16 :: c:c1:c2
hole_0':s2_16 :: 0':s
hole_c3:c43_16 :: c3:c4
hole_nil:cons4_16 :: nil:cons
hole_c5:c65_16 :: c5:c6
hole_c7:c86_16 :: c7:c8
hole_true:false7_16 :: true:false
hole_c9:c108_16 :: c9:c10
hole_c11:c129_16 :: c11:c12
hole_c13:c14:c1510_16 :: c13:c14:c15
gen_c:c1:c211_16 :: Nat -> c:c1:c2
gen_0':s12_16 :: Nat -> 0':s
gen_c3:c413_16 :: Nat -> c3:c4
gen_nil:cons14_16 :: Nat -> nil:cons
gen_c13:c14:c1515_16 :: Nat -> c13:c14:c15


Lemmas:
LE(gen_0':s12_16(n17_16), gen_0':s12_16(n17_16)) -> gen_c:c1:c211_16(n17_16), rt in Omega(1 + n17_16)
APP(gen_nil:cons14_16(n650_16), gen_nil:cons14_16(b)) -> gen_c3:c413_16(n650_16), rt in Omega(1 + n650_16)
le(gen_0':s12_16(n1477_16), gen_0':s12_16(n1477_16)) -> true, rt in Omega(0)
LOW(gen_0':s12_16(0), gen_nil:cons14_16(n1878_16)) -> *16_16, rt in Omega(n1878_16)
HIGH(gen_0':s12_16(0), gen_nil:cons14_16(n7251_16)) -> *16_16, rt in Omega(n7251_16)
low(gen_0':s12_16(0), gen_nil:cons14_16(n15532_16)) -> gen_nil:cons14_16(n15532_16), rt in Omega(0)
high(gen_0':s12_16(0), gen_nil:cons14_16(n16816_16)) -> gen_nil:cons14_16(0), rt in Omega(0)
app(gen_nil:cons14_16(n18030_16), gen_nil:cons14_16(b)) -> gen_nil:cons14_16(+(n18030_16, b)), rt in Omega(0)
quicksort(gen_nil:cons14_16(n20145_16)) -> gen_nil:cons14_16(n20145_16), rt in Omega(0)


Generator Equations:
gen_c:c1:c211_16(0) <=> c
gen_c:c1:c211_16(+(x, 1)) <=> c2(gen_c:c1:c211_16(x))
gen_0':s12_16(0) <=> 0'
gen_0':s12_16(+(x, 1)) <=> s(gen_0':s12_16(x))
gen_c3:c413_16(0) <=> c3
gen_c3:c413_16(+(x, 1)) <=> c4(gen_c3:c413_16(x))
gen_nil:cons14_16(0) <=> nil
gen_nil:cons14_16(+(x, 1)) <=> cons(0', gen_nil:cons14_16(x))
gen_c13:c14:c1515_16(0) <=> c13
gen_c13:c14:c1515_16(+(x, 1)) <=> c14(c3, gen_c13:c14:c1515_16(x), c5)


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

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

(36)
BOUNDS(n^2, INF)