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


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


WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxRelTRS
(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 159 ms]
(2) CpxRelTRS
(3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CpxRelTRS
(5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) typed CpxTrs
(7) OrderProof [LOWER BOUND(ID), 0 ms]
(8) typed CpxTrs
(9) RewriteLemmaProof [LOWER BOUND(ID), 306 ms]
(10) typed CpxTrs
(11) RewriteLemmaProof [LOWER BOUND(ID), 36 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), 46 ms]
        (18) typed CpxTrs
        (19) RewriteLemmaProof [LOWER BOUND(ID), 41 ms]
        (20) typed CpxTrs
        (21) RewriteLemmaProof [LOWER BOUND(ID), 75 ms]
        (22) typed CpxTrs


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

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


The TRS R consists of the following rules:

   quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
   quicksort(Cons(x, Nil)) -> Cons(x, Nil)
   quicksort(Nil) -> Nil
   partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
   partLt(x, Nil) -> Nil
   partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
   partGt(x, Nil) -> Nil
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
   app(Nil, ys) -> ys
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
   goal(xs) -> quicksort(xs)

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
   partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
   partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
   partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
   partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

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

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

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


The TRS R consists of the following rules:

   quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
   quicksort(Cons(x, Nil)) -> Cons(x, Nil)
   quicksort(Nil) -> Nil
   partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
   partLt(x, Nil) -> Nil
   partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
   partGt(x, Nil) -> Nil
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
   app(Nil, ys) -> ys
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
   goal(xs) -> quicksort(xs)

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
   partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
   partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
   partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
   partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

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

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

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


The TRS R consists of the following rules:

   quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
   quicksort(Cons(x, Nil)) -> Cons(x, Nil)
   quicksort(Nil) -> Nil
   partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
   partLt(x, Nil) -> Nil
   partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
   partGt(x, Nil) -> Nil
   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
   app(Nil, ys) -> ys
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
   goal(xs) -> quicksort(xs)

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
   partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
   partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
   partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
   partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

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

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

(6)
Obligation:
Innermost TRS:
Rules:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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'

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

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

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

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

(8)
Obligation:
Innermost TRS:
Rules:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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:
<, quicksort, partLt, partGt, >, app

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

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

(9) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_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(+(n7_0, 1)), gen_S:0'5_0(+(1, +(n7_0, 1)))) ->_R^Omega(0)
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) ->_IH
True

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

(10)
Obligation:
Innermost TRS:
Rules:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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:
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_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:
partLt, quicksort, partGt, >, app

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

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

(11) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(n299_0)) -> gen_Cons:Nil4_0(n299_0), rt in Omega(1 + n299_0)

Induction Base:
partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(0)) ->_R^Omega(1)
Nil

Induction Step:
partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(+(n299_0, 1))) ->_R^Omega(1)
partLt[Ite][True][Ite](<(0', gen_S:0'5_0(1)), gen_S:0'5_0(1), Cons(0', gen_Cons:Nil4_0(n299_0))) ->_L^Omega(0)
partLt[Ite][True][Ite](True, gen_S:0'5_0(1), Cons(0', gen_Cons:Nil4_0(n299_0))) ->_R^Omega(0)
Cons(0', partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(n299_0))) ->_IH
Cons(0', gen_Cons:Nil4_0(c300_0))

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:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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:
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_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:
partLt, quicksort, partGt, >, app

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

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

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

(15)
BOUNDS(n^1, INF)

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

(16)
Obligation:
Innermost TRS:
Rules:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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:
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> True, rt in Omega(0)
partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(n299_0)) -> gen_Cons:Nil4_0(n299_0), rt in Omega(1 + n299_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, partGt, app

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

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
>(gen_S:0'5_0(n1026_0), gen_S:0'5_0(n1026_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(+(n1026_0, 1)), gen_S:0'5_0(+(n1026_0, 1))) ->_R^Omega(0)
>(gen_S:0'5_0(n1026_0), gen_S:0'5_0(n1026_0)) ->_IH
False

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

(18)
Obligation:
Innermost TRS:
Rules:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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:
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> True, rt in Omega(0)
partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(n299_0)) -> gen_Cons:Nil4_0(n299_0), rt in Omega(1 + n299_0)
>(gen_S:0'5_0(n1026_0), gen_S:0'5_0(n1026_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:
partGt, quicksort, app

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

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

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
partGt(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1331_0)) -> gen_Cons:Nil4_0(0), rt in Omega(1 + n1331_0)

Induction Base:
partGt(gen_S:0'5_0(0), gen_Cons:Nil4_0(0)) ->_R^Omega(1)
Nil

Induction Step:
partGt(gen_S:0'5_0(0), gen_Cons:Nil4_0(+(n1331_0, 1))) ->_R^Omega(1)
partGt[Ite][True][Ite](>(0', gen_S:0'5_0(0)), gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1331_0))) ->_L^Omega(0)
partGt[Ite][True][Ite](False, gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1331_0))) ->_R^Omega(0)
partGt(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1331_0)) ->_IH
gen_Cons:Nil4_0(0)

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

(20)
Obligation:
Innermost TRS:
Rules:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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:
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> True, rt in Omega(0)
partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(n299_0)) -> gen_Cons:Nil4_0(n299_0), rt in Omega(1 + n299_0)
>(gen_S:0'5_0(n1026_0), gen_S:0'5_0(n1026_0)) -> False, rt in Omega(0)
partGt(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1331_0)) -> gen_Cons:Nil4_0(0), rt in Omega(1 + n1331_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

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

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
app(gen_Cons:Nil4_0(n2095_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n2095_0, b)), rt in Omega(1 + n2095_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(+(n2095_0, 1)), gen_Cons:Nil4_0(b)) ->_R^Omega(1)
Cons(0', app(gen_Cons:Nil4_0(n2095_0), gen_Cons:Nil4_0(b))) ->_IH
Cons(0', gen_Cons:Nil4_0(+(b, c2096_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:
quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x', xs))
quicksort(Cons(x, Nil)) -> Cons(x, Nil)
quicksort(Nil) -> Nil
partLt(x', Cons(x, xs)) -> partLt[Ite][True][Ite](<(x, x'), x', Cons(x, xs))
partLt(x, Nil) -> Nil
partGt(x', Cons(x, xs)) -> partGt[Ite][True][Ite](>(x, x'), x', Cons(x, xs))
partGt(x, Nil) -> Nil
app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
app(Nil, ys) -> ys
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
part(x, xs) -> app(quicksort(partLt(x, xs)), Cons(x, quicksort(partGt(x, xs))))
goal(xs) -> quicksort(xs)
<(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
partLt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partLt(x', xs))
partGt[Ite][True][Ite](True, x', Cons(x, xs)) -> Cons(x, partGt(x', xs))
partLt[Ite][True][Ite](False, x', Cons(x, xs)) -> partLt(x', xs)
partGt[Ite][True][Ite](False, x', Cons(x, xs)) -> partGt(x', xs)

Types:
quicksort :: Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
part :: S:0' -> Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
partLt :: S:0' -> Cons:Nil -> Cons:Nil
partLt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
partGt :: S:0' -> Cons:Nil -> Cons:Nil
partGt[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
> :: S:0' -> S:0' -> True:False
app :: Cons:Nil -> Cons:Nil -> Cons:Nil
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
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:
<(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> True, rt in Omega(0)
partLt(gen_S:0'5_0(1), gen_Cons:Nil4_0(n299_0)) -> gen_Cons:Nil4_0(n299_0), rt in Omega(1 + n299_0)
>(gen_S:0'5_0(n1026_0), gen_S:0'5_0(n1026_0)) -> False, rt in Omega(0)
partGt(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1331_0)) -> gen_Cons:Nil4_0(0), rt in Omega(1 + n1331_0)
app(gen_Cons:Nil4_0(n2095_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n2095_0, b)), rt in Omega(1 + n2095_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