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