1124.73/291.47 WORST_CASE(Omega(n^1), ?) 1132.63/293.45 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1132.63/293.45 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1132.63/293.45 1132.63/293.45 1132.63/293.45 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1132.63/293.45 1132.63/293.45 (0) CpxRelTRS 1132.63/293.45 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 331 ms] 1132.63/293.45 (2) CpxRelTRS 1132.63/293.45 (3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1132.63/293.45 (4) CpxRelTRS 1132.63/293.45 (5) SlicingProof [LOWER BOUND(ID), 0 ms] 1132.63/293.45 (6) CpxRelTRS 1132.63/293.45 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1132.63/293.45 (8) typed CpxTrs 1132.63/293.45 (9) OrderProof [LOWER BOUND(ID), 0 ms] 1132.63/293.45 (10) typed CpxTrs 1132.63/293.45 (11) RewriteLemmaProof [LOWER BOUND(ID), 241 ms] 1132.63/293.45 (12) typed CpxTrs 1132.63/293.45 (13) RewriteLemmaProof [LOWER BOUND(ID), 61 ms] 1132.63/293.45 (14) BEST 1132.63/293.45 (15) proven lower bound 1132.63/293.45 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1132.63/293.45 (17) BOUNDS(n^1, INF) 1132.63/293.45 (18) typed CpxTrs 1132.63/293.45 (19) RewriteLemmaProof [LOWER BOUND(ID), 51 ms] 1132.63/293.45 (20) typed CpxTrs 1132.63/293.45 1132.63/293.45 1132.63/293.45 ---------------------------------------- 1132.63/293.45 1132.63/293.45 (0) 1132.63/293.45 Obligation: 1132.63/293.45 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1132.63/293.46 1132.63/293.46 1132.63/293.46 The TRS R consists of the following rules: 1132.63/293.46 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 1132.63/293.46 The (relative) TRS S consists of the following rules: 1132.63/293.46 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0, S(y)) -> True 1132.63/293.46 <(x, 0) -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0, y) -> False 1132.63/293.46 >(S(x), 0) -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 1132.63/293.46 Rewrite Strategy: INNERMOST 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 1132.63/293.46 proved termination of relative rules 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (2) 1132.63/293.46 Obligation: 1132.63/293.46 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1132.63/293.46 1132.63/293.46 1132.63/293.46 The TRS R consists of the following rules: 1132.63/293.46 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 1132.63/293.46 The (relative) TRS S consists of the following rules: 1132.63/293.46 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0, S(y)) -> True 1132.63/293.46 <(x, 0) -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0, y) -> False 1132.63/293.46 >(S(x), 0) -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 1132.63/293.46 Rewrite Strategy: INNERMOST 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (3) RenamingProof (BOTH BOUNDS(ID, ID)) 1132.63/293.46 Renamed function symbols to avoid clashes with predefined symbol. 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (4) 1132.63/293.46 Obligation: 1132.63/293.46 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1132.63/293.46 1132.63/293.46 1132.63/293.46 The TRS R consists of the following rules: 1132.63/293.46 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 1132.63/293.46 The (relative) TRS S consists of the following rules: 1132.63/293.46 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 1132.63/293.46 Rewrite Strategy: INNERMOST 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (5) SlicingProof (LOWER BOUND(ID)) 1132.63/293.46 Sliced the following arguments: 1132.63/293.46 part[Ite][True][Ite][False][Ite]/1 1132.63/293.46 part[Ite][True][Ite][False][Ite]/2 1132.63/293.46 part[Ite][True][Ite][False][Ite]/3 1132.63/293.46 part[Ite][True][Ite][False][Ite]/4 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (6) 1132.63/293.46 Obligation: 1132.63/293.46 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1132.63/293.46 1132.63/293.46 1132.63/293.46 The TRS R consists of the following rules: 1132.63/293.46 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 1132.63/293.46 The (relative) TRS S consists of the following rules: 1132.63/293.46 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x)) 1132.63/293.46 1132.63/293.46 Rewrite Strategy: INNERMOST 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1132.63/293.46 Infered types. 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (8) 1132.63/293.46 Obligation: 1132.63/293.46 Innermost TRS: 1132.63/293.46 Rules: 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x)) 1132.63/293.46 1132.63/293.46 Types: 1132.63/293.46 quicksort :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Cons :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Nil :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 > :: S:0' -> S:0' -> True:False 1132.63/293.46 app :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 notEmpty :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> True:False 1132.63/293.46 True :: True:False 1132.63/293.46 False :: True:False 1132.63/293.46 goal :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 < :: S:0' -> S:0' -> True:False 1132.63/293.46 S :: S:0' -> S:0' 1132.63/293.46 0' :: S:0' 1132.63/293.46 part[Ite][True][Ite][False][Ite] :: True:False -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_Cons:Nil:part[Ite][True][Ite][False][Ite]1_0 :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_S:0'2_0 :: S:0' 1132.63/293.46 hole_True:False3_0 :: True:False 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0 :: Nat -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 gen_S:0'5_0 :: Nat -> S:0' 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (9) OrderProof (LOWER BOUND(ID)) 1132.63/293.46 Heuristically decided to analyse the following defined symbols: 1132.63/293.46 quicksort, part, >, app, < 1132.63/293.46 1132.63/293.46 They will be analysed ascendingly in the following order: 1132.63/293.46 quicksort = part 1132.63/293.46 > < part 1132.63/293.46 app < part 1132.63/293.46 < < part 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (10) 1132.63/293.46 Obligation: 1132.63/293.46 Innermost TRS: 1132.63/293.46 Rules: 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x)) 1132.63/293.46 1132.63/293.46 Types: 1132.63/293.46 quicksort :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Cons :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Nil :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 > :: S:0' -> S:0' -> True:False 1132.63/293.46 app :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 notEmpty :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> True:False 1132.63/293.46 True :: True:False 1132.63/293.46 False :: True:False 1132.63/293.46 goal :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 < :: S:0' -> S:0' -> True:False 1132.63/293.46 S :: S:0' -> S:0' 1132.63/293.46 0' :: S:0' 1132.63/293.46 part[Ite][True][Ite][False][Ite] :: True:False -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_Cons:Nil:part[Ite][True][Ite][False][Ite]1_0 :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_S:0'2_0 :: S:0' 1132.63/293.46 hole_True:False3_0 :: True:False 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0 :: Nat -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 gen_S:0'5_0 :: Nat -> S:0' 1132.63/293.46 1132.63/293.46 1132.63/293.46 Generator Equations: 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(0) <=> Nil 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(x)) 1132.63/293.46 gen_S:0'5_0(0) <=> 0' 1132.63/293.46 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 1132.63/293.46 1132.63/293.46 1132.63/293.46 The following defined symbols remain to be analysed: 1132.63/293.46 >, quicksort, part, app, < 1132.63/293.46 1132.63/293.46 They will be analysed ascendingly in the following order: 1132.63/293.46 quicksort = part 1132.63/293.46 > < part 1132.63/293.46 app < part 1132.63/293.46 < < part 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (11) RewriteLemmaProof (LOWER BOUND(ID)) 1132.63/293.46 Proved the following rewrite lemma: 1132.63/293.46 >(gen_S:0'5_0(n7_0), gen_S:0'5_0(n7_0)) -> False, rt in Omega(0) 1132.63/293.46 1132.63/293.46 Induction Base: 1132.63/293.46 >(gen_S:0'5_0(0), gen_S:0'5_0(0)) ->_R^Omega(0) 1132.63/293.46 False 1132.63/293.46 1132.63/293.46 Induction Step: 1132.63/293.46 >(gen_S:0'5_0(+(n7_0, 1)), gen_S:0'5_0(+(n7_0, 1))) ->_R^Omega(0) 1132.63/293.46 >(gen_S:0'5_0(n7_0), gen_S:0'5_0(n7_0)) ->_IH 1132.63/293.46 False 1132.63/293.46 1132.63/293.46 We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (12) 1132.63/293.46 Obligation: 1132.63/293.46 Innermost TRS: 1132.63/293.46 Rules: 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x)) 1132.63/293.46 1132.63/293.46 Types: 1132.63/293.46 quicksort :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Cons :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Nil :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 > :: S:0' -> S:0' -> True:False 1132.63/293.46 app :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 notEmpty :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> True:False 1132.63/293.46 True :: True:False 1132.63/293.46 False :: True:False 1132.63/293.46 goal :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 < :: S:0' -> S:0' -> True:False 1132.63/293.46 S :: S:0' -> S:0' 1132.63/293.46 0' :: S:0' 1132.63/293.46 part[Ite][True][Ite][False][Ite] :: True:False -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_Cons:Nil:part[Ite][True][Ite][False][Ite]1_0 :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_S:0'2_0 :: S:0' 1132.63/293.46 hole_True:False3_0 :: True:False 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0 :: Nat -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 gen_S:0'5_0 :: Nat -> S:0' 1132.63/293.46 1132.63/293.46 1132.63/293.46 Lemmas: 1132.63/293.46 >(gen_S:0'5_0(n7_0), gen_S:0'5_0(n7_0)) -> False, rt in Omega(0) 1132.63/293.46 1132.63/293.46 1132.63/293.46 Generator Equations: 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(0) <=> Nil 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(x)) 1132.63/293.46 gen_S:0'5_0(0) <=> 0' 1132.63/293.46 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 1132.63/293.46 1132.63/293.46 1132.63/293.46 The following defined symbols remain to be analysed: 1132.63/293.46 app, quicksort, part, < 1132.63/293.46 1132.63/293.46 They will be analysed ascendingly in the following order: 1132.63/293.46 quicksort = part 1132.63/293.46 app < part 1132.63/293.46 < < part 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1132.63/293.46 Proved the following rewrite lemma: 1132.63/293.46 app(gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(n270_0), gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(b)) -> gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(n270_0, b)), rt in Omega(1 + n270_0) 1132.63/293.46 1132.63/293.46 Induction Base: 1132.63/293.46 app(gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(0), gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(b)) ->_R^Omega(1) 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(b) 1132.63/293.46 1132.63/293.46 Induction Step: 1132.63/293.46 app(gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(n270_0, 1)), gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(b)) ->_R^Omega(1) 1132.63/293.46 Cons(0', app(gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(n270_0), gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(b))) ->_IH 1132.63/293.46 Cons(0', gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(b, c271_0))) 1132.63/293.46 1132.63/293.46 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (14) 1132.63/293.46 Complex Obligation (BEST) 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (15) 1132.63/293.46 Obligation: 1132.63/293.46 Proved the lower bound n^1 for the following obligation: 1132.63/293.46 1132.63/293.46 Innermost TRS: 1132.63/293.46 Rules: 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x)) 1132.63/293.46 1132.63/293.46 Types: 1132.63/293.46 quicksort :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Cons :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Nil :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 > :: S:0' -> S:0' -> True:False 1132.63/293.46 app :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 notEmpty :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> True:False 1132.63/293.46 True :: True:False 1132.63/293.46 False :: True:False 1132.63/293.46 goal :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 < :: S:0' -> S:0' -> True:False 1132.63/293.46 S :: S:0' -> S:0' 1132.63/293.46 0' :: S:0' 1132.63/293.46 part[Ite][True][Ite][False][Ite] :: True:False -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_Cons:Nil:part[Ite][True][Ite][False][Ite]1_0 :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_S:0'2_0 :: S:0' 1132.63/293.46 hole_True:False3_0 :: True:False 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0 :: Nat -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 gen_S:0'5_0 :: Nat -> S:0' 1132.63/293.46 1132.63/293.46 1132.63/293.46 Lemmas: 1132.63/293.46 >(gen_S:0'5_0(n7_0), gen_S:0'5_0(n7_0)) -> False, rt in Omega(0) 1132.63/293.46 1132.63/293.46 1132.63/293.46 Generator Equations: 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(0) <=> Nil 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(x)) 1132.63/293.46 gen_S:0'5_0(0) <=> 0' 1132.63/293.46 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 1132.63/293.46 1132.63/293.46 1132.63/293.46 The following defined symbols remain to be analysed: 1132.63/293.46 app, quicksort, part, < 1132.63/293.46 1132.63/293.46 They will be analysed ascendingly in the following order: 1132.63/293.46 quicksort = part 1132.63/293.46 app < part 1132.63/293.46 < < part 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (16) LowerBoundPropagationProof (FINISHED) 1132.63/293.46 Propagated lower bound. 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (17) 1132.63/293.46 BOUNDS(n^1, INF) 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (18) 1132.63/293.46 Obligation: 1132.63/293.46 Innermost TRS: 1132.63/293.46 Rules: 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x)) 1132.63/293.46 1132.63/293.46 Types: 1132.63/293.46 quicksort :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Cons :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Nil :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 > :: S:0' -> S:0' -> True:False 1132.63/293.46 app :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 notEmpty :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> True:False 1132.63/293.46 True :: True:False 1132.63/293.46 False :: True:False 1132.63/293.46 goal :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 < :: S:0' -> S:0' -> True:False 1132.63/293.46 S :: S:0' -> S:0' 1132.63/293.46 0' :: S:0' 1132.63/293.46 part[Ite][True][Ite][False][Ite] :: True:False -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_Cons:Nil:part[Ite][True][Ite][False][Ite]1_0 :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_S:0'2_0 :: S:0' 1132.63/293.46 hole_True:False3_0 :: True:False 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0 :: Nat -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 gen_S:0'5_0 :: Nat -> S:0' 1132.63/293.46 1132.63/293.46 1132.63/293.46 Lemmas: 1132.63/293.46 >(gen_S:0'5_0(n7_0), gen_S:0'5_0(n7_0)) -> False, rt in Omega(0) 1132.63/293.46 app(gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(n270_0), gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(b)) -> gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(n270_0, b)), rt in Omega(1 + n270_0) 1132.63/293.46 1132.63/293.46 1132.63/293.46 Generator Equations: 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(0) <=> Nil 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(x)) 1132.63/293.46 gen_S:0'5_0(0) <=> 0' 1132.63/293.46 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 1132.63/293.46 1132.63/293.46 1132.63/293.46 The following defined symbols remain to be analysed: 1132.63/293.46 <, quicksort, part 1132.63/293.46 1132.63/293.46 They will be analysed ascendingly in the following order: 1132.63/293.46 quicksort = part 1132.63/293.46 < < part 1132.63/293.46 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1132.63/293.46 Proved the following rewrite lemma: 1132.63/293.46 <(gen_S:0'5_0(n1121_0), gen_S:0'5_0(+(1, n1121_0))) -> True, rt in Omega(0) 1132.63/293.46 1132.63/293.46 Induction Base: 1132.63/293.46 <(gen_S:0'5_0(0), gen_S:0'5_0(+(1, 0))) ->_R^Omega(0) 1132.63/293.46 True 1132.63/293.46 1132.63/293.46 Induction Step: 1132.63/293.46 <(gen_S:0'5_0(+(n1121_0, 1)), gen_S:0'5_0(+(1, +(n1121_0, 1)))) ->_R^Omega(0) 1132.63/293.46 <(gen_S:0'5_0(n1121_0), gen_S:0'5_0(+(1, n1121_0))) ->_IH 1132.63/293.46 True 1132.63/293.46 1132.63/293.46 We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). 1132.63/293.46 ---------------------------------------- 1132.63/293.46 1132.63/293.46 (20) 1132.63/293.46 Obligation: 1132.63/293.46 Innermost TRS: 1132.63/293.46 Rules: 1132.63/293.46 quicksort(Cons(x, Cons(x', xs))) -> part(x, Cons(x, Cons(x', xs)), Cons(x, Nil), Nil) 1132.63/293.46 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 1132.63/293.46 quicksort(Nil) -> Nil 1132.63/293.46 part(x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 1132.63/293.46 part(x, Nil, xs1, xs2) -> app(quicksort(xs1), quicksort(xs2)) 1132.63/293.46 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 1132.63/293.46 app(Nil, ys) -> ys 1132.63/293.46 notEmpty(Cons(x, xs)) -> True 1132.63/293.46 notEmpty(Nil) -> False 1132.63/293.46 goal(xs) -> quicksort(xs) 1132.63/293.46 <(S(x), S(y)) -> <(x, y) 1132.63/293.46 <(0', S(y)) -> True 1132.63/293.46 <(x, 0') -> False 1132.63/293.46 >(S(x), S(y)) -> >(x, y) 1132.63/293.46 >(0', y) -> False 1132.63/293.46 >(S(x), 0') -> True 1132.63/293.46 part[Ite][True][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 1132.63/293.46 part[Ite][True][Ite](False, x', Cons(x, xs), xs1, xs2) -> part[Ite][True][Ite][False][Ite](<(x', x)) 1132.63/293.46 1132.63/293.46 Types: 1132.63/293.46 quicksort :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Cons :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part :: S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 Nil :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 part[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 > :: S:0' -> S:0' -> True:False 1132.63/293.46 app :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 notEmpty :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> True:False 1132.63/293.46 True :: True:False 1132.63/293.46 False :: True:False 1132.63/293.46 goal :: Cons:Nil:part[Ite][True][Ite][False][Ite] -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 < :: S:0' -> S:0' -> True:False 1132.63/293.46 S :: S:0' -> S:0' 1132.63/293.46 0' :: S:0' 1132.63/293.46 part[Ite][True][Ite][False][Ite] :: True:False -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_Cons:Nil:part[Ite][True][Ite][False][Ite]1_0 :: Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 hole_S:0'2_0 :: S:0' 1132.63/293.46 hole_True:False3_0 :: True:False 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0 :: Nat -> Cons:Nil:part[Ite][True][Ite][False][Ite] 1132.63/293.46 gen_S:0'5_0 :: Nat -> S:0' 1132.63/293.46 1132.63/293.46 1132.63/293.46 Lemmas: 1132.63/293.46 >(gen_S:0'5_0(n7_0), gen_S:0'5_0(n7_0)) -> False, rt in Omega(0) 1132.63/293.46 app(gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(n270_0), gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(b)) -> gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(n270_0, b)), rt in Omega(1 + n270_0) 1132.63/293.46 <(gen_S:0'5_0(n1121_0), gen_S:0'5_0(+(1, n1121_0))) -> True, rt in Omega(0) 1132.63/293.46 1132.63/293.46 1132.63/293.46 Generator Equations: 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(0) <=> Nil 1132.63/293.46 gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil:part[Ite][True][Ite][False][Ite]4_0(x)) 1132.63/293.46 gen_S:0'5_0(0) <=> 0' 1132.63/293.46 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 1132.63/293.46 1132.63/293.46 1132.63/293.46 The following defined symbols remain to be analysed: 1132.63/293.46 part, quicksort 1132.63/293.46 1132.63/293.46 They will be analysed ascendingly in the following order: 1132.63/293.46 quicksort = part 1132.80/293.52 EOF