355.20/291.53 WORST_CASE(Omega(n^1), O(n^2)) 355.20/291.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 355.20/291.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 355.20/291.55 355.20/291.55 355.20/291.55 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 355.20/291.55 355.20/291.55 (0) CpxRelTRS 355.20/291.55 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 421 ms] 355.20/291.55 (2) CpxRelTRS 355.20/291.55 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 355.20/291.55 (4) CpxWeightedTrs 355.20/291.55 (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 355.20/291.55 (6) CpxWeightedTrs 355.20/291.55 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 355.20/291.55 (8) CpxTypedWeightedTrs 355.20/291.55 (9) CompletionProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (10) CpxTypedWeightedCompleteTrs 355.20/291.55 (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 355.20/291.55 (12) CpxTypedWeightedCompleteTrs 355.20/291.55 (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 1 ms] 355.20/291.55 (14) CpxRNTS 355.20/291.55 (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 355.20/291.55 (16) CpxRNTS 355.20/291.55 (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 2 ms] 355.20/291.55 (18) CpxRNTS 355.20/291.55 (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (20) CpxRNTS 355.20/291.55 (21) IntTrsBoundProof [UPPER BOUND(ID), 158 ms] 355.20/291.55 (22) CpxRNTS 355.20/291.55 (23) IntTrsBoundProof [UPPER BOUND(ID), 48 ms] 355.20/291.55 (24) CpxRNTS 355.20/291.55 (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (26) CpxRNTS 355.20/291.55 (27) IntTrsBoundProof [UPPER BOUND(ID), 413 ms] 355.20/291.55 (28) CpxRNTS 355.20/291.55 (29) IntTrsBoundProof [UPPER BOUND(ID), 90 ms] 355.20/291.55 (30) CpxRNTS 355.20/291.55 (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (32) CpxRNTS 355.20/291.55 (33) IntTrsBoundProof [UPPER BOUND(ID), 502 ms] 355.20/291.55 (34) CpxRNTS 355.20/291.55 (35) IntTrsBoundProof [UPPER BOUND(ID), 155 ms] 355.20/291.55 (36) CpxRNTS 355.20/291.55 (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (38) CpxRNTS 355.20/291.55 (39) IntTrsBoundProof [UPPER BOUND(ID), 450 ms] 355.20/291.55 (40) CpxRNTS 355.20/291.55 (41) IntTrsBoundProof [UPPER BOUND(ID), 105 ms] 355.20/291.55 (42) CpxRNTS 355.20/291.55 (43) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (44) CpxRNTS 355.20/291.55 (45) IntTrsBoundProof [UPPER BOUND(ID), 4185 ms] 355.20/291.55 (46) CpxRNTS 355.20/291.55 (47) IntTrsBoundProof [UPPER BOUND(ID), 1640 ms] 355.20/291.55 (48) CpxRNTS 355.20/291.55 (49) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (50) CpxRNTS 355.20/291.55 (51) IntTrsBoundProof [UPPER BOUND(ID), 713 ms] 355.20/291.55 (52) CpxRNTS 355.20/291.55 (53) IntTrsBoundProof [UPPER BOUND(ID), 266 ms] 355.20/291.55 (54) CpxRNTS 355.20/291.55 (55) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (56) CpxRNTS 355.20/291.55 (57) IntTrsBoundProof [UPPER BOUND(ID), 189 ms] 355.20/291.55 (58) CpxRNTS 355.20/291.55 (59) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 355.20/291.55 (60) CpxRNTS 355.20/291.55 (61) FinalProof [FINISHED, 0 ms] 355.20/291.55 (62) BOUNDS(1, n^2) 355.20/291.55 (63) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 355.20/291.55 (64) CpxRelTRS 355.20/291.55 (65) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 355.20/291.55 (66) typed CpxTrs 355.20/291.55 (67) OrderProof [LOWER BOUND(ID), 0 ms] 355.20/291.55 (68) typed CpxTrs 355.20/291.55 (69) RewriteLemmaProof [LOWER BOUND(ID), 287 ms] 355.20/291.55 (70) BEST 355.20/291.55 (71) proven lower bound 355.20/291.55 (72) LowerBoundPropagationProof [FINISHED, 0 ms] 355.20/291.55 (73) BOUNDS(n^1, INF) 355.20/291.55 (74) typed CpxTrs 355.20/291.55 (75) RewriteLemmaProof [LOWER BOUND(ID), 61 ms] 355.20/291.55 (76) typed CpxTrs 355.20/291.55 (77) RewriteLemmaProof [LOWER BOUND(ID), 48 ms] 355.20/291.55 (78) typed CpxTrs 355.20/291.55 (79) RewriteLemmaProof [LOWER BOUND(ID), 91 ms] 355.20/291.55 (80) typed CpxTrs 355.20/291.55 355.20/291.55 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (0) 355.20/291.55 Obligation: 355.20/291.55 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 355.20/291.55 355.20/291.55 355.20/291.55 The TRS R consists of the following rules: 355.20/291.55 355.20/291.55 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.55 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.55 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.55 quicksort(Nil) -> Nil 355.20/291.55 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.55 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.55 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.55 app(Nil, ys) -> ys 355.20/291.55 notEmpty(Cons(x, xs)) -> True 355.20/291.55 notEmpty(Nil) -> False 355.20/291.55 355.20/291.55 The (relative) TRS S consists of the following rules: 355.20/291.55 355.20/291.55 <(S(x), S(y)) -> <(x, y) 355.20/291.55 <(0, S(y)) -> True 355.20/291.55 <(x, 0) -> False 355.20/291.55 >(S(x), S(y)) -> >(x, y) 355.20/291.55 >(0, y) -> False 355.20/291.55 >(S(x), 0) -> True 355.20/291.55 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.55 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.55 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.55 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.55 355.20/291.55 Rewrite Strategy: INNERMOST 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 355.20/291.55 proved termination of relative rules 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (2) 355.20/291.55 Obligation: 355.20/291.55 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 355.20/291.55 355.20/291.55 355.20/291.55 The TRS R consists of the following rules: 355.20/291.55 355.20/291.55 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.55 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.55 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.55 quicksort(Nil) -> Nil 355.20/291.55 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.55 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.55 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.55 app(Nil, ys) -> ys 355.20/291.55 notEmpty(Cons(x, xs)) -> True 355.20/291.55 notEmpty(Nil) -> False 355.20/291.55 355.20/291.55 The (relative) TRS S consists of the following rules: 355.20/291.55 355.20/291.55 <(S(x), S(y)) -> <(x, y) 355.20/291.55 <(0, S(y)) -> True 355.20/291.55 <(x, 0) -> False 355.20/291.55 >(S(x), S(y)) -> >(x, y) 355.20/291.55 >(0, y) -> False 355.20/291.55 >(S(x), 0) -> True 355.20/291.55 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.55 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.55 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.55 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.55 355.20/291.55 Rewrite Strategy: INNERMOST 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 355.20/291.55 Transformed relative TRS to weighted TRS 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (4) 355.20/291.55 Obligation: 355.20/291.55 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 355.20/291.55 355.20/291.55 355.20/291.55 The TRS R consists of the following rules: 355.20/291.55 355.20/291.55 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1] 355.20/291.55 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1] 355.20/291.55 quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1] 355.20/291.55 quicksort(Nil) -> Nil [1] 355.20/291.55 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) [1] 355.20/291.55 part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1] 355.20/291.55 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1] 355.20/291.55 app(Nil, ys) -> ys [1] 355.20/291.55 notEmpty(Cons(x, xs)) -> True [1] 355.20/291.55 notEmpty(Nil) -> False [1] 355.20/291.55 <(S(x), S(y)) -> <(x, y) [0] 355.20/291.55 <(0, S(y)) -> True [0] 355.20/291.55 <(x, 0) -> False [0] 355.20/291.55 >(S(x), S(y)) -> >(x, y) [0] 355.20/291.55 >(0, y) -> False [0] 355.20/291.55 >(S(x), 0) -> True [0] 355.20/291.55 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0] 355.20/291.55 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0] 355.20/291.55 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) [0] 355.20/291.55 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0] 355.20/291.55 355.20/291.55 Rewrite Strategy: INNERMOST 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) 355.20/291.55 Renamed defined symbols to avoid conflicts with arithmetic symbols: 355.20/291.55 355.20/291.55 > => gr 355.20/291.55 < => lt 355.20/291.55 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (6) 355.20/291.55 Obligation: 355.20/291.55 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 355.20/291.55 355.20/291.55 355.20/291.55 The TRS R consists of the following rules: 355.20/291.55 355.20/291.55 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1] 355.20/291.55 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1] 355.20/291.55 quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1] 355.20/291.55 quicksort(Nil) -> Nil [1] 355.20/291.55 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](gr(x', x), x', Cons(x, xs), xs1, xs2) [1] 355.20/291.55 part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1] 355.20/291.55 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1] 355.20/291.55 app(Nil, ys) -> ys [1] 355.20/291.55 notEmpty(Cons(x, xs)) -> True [1] 355.20/291.55 notEmpty(Nil) -> False [1] 355.20/291.55 lt(S(x), S(y)) -> lt(x, y) [0] 355.20/291.55 lt(0, S(y)) -> True [0] 355.20/291.55 lt(x, 0) -> False [0] 355.20/291.55 gr(S(x), S(y)) -> gr(x, y) [0] 355.20/291.55 gr(0, y) -> False [0] 355.20/291.55 gr(S(x), 0) -> True [0] 355.20/291.55 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0] 355.20/291.55 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0] 355.20/291.55 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](lt(x', x), x', Cons(x, xs), xs1, xs2) [0] 355.20/291.55 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0] 355.20/291.55 355.20/291.55 Rewrite Strategy: INNERMOST 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 355.20/291.55 Infered types. 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (8) 355.20/291.55 Obligation: 355.20/291.55 Runtime Complexity Weighted TRS with Types. 355.20/291.55 The TRS R consists of the following rules: 355.20/291.55 355.20/291.55 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1] 355.20/291.55 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1] 355.20/291.55 quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1] 355.20/291.55 quicksort(Nil) -> Nil [1] 355.20/291.55 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](gr(x', x), x', Cons(x, xs), xs1, xs2) [1] 355.20/291.55 part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1] 355.20/291.55 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1] 355.20/291.55 app(Nil, ys) -> ys [1] 355.20/291.55 notEmpty(Cons(x, xs)) -> True [1] 355.20/291.55 notEmpty(Nil) -> False [1] 355.20/291.55 lt(S(x), S(y)) -> lt(x, y) [0] 355.20/291.55 lt(0, S(y)) -> True [0] 355.20/291.55 lt(x, 0) -> False [0] 355.20/291.55 gr(S(x), S(y)) -> gr(x, y) [0] 355.20/291.55 gr(0, y) -> False [0] 355.20/291.55 gr(S(x), 0) -> True [0] 355.20/291.55 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0] 355.20/291.55 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0] 355.20/291.55 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](lt(x', x), x', Cons(x, xs), xs1, xs2) [0] 355.20/291.55 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0] 355.20/291.55 355.20/291.55 The TRS has the following type information: 355.20/291.55 qs :: S:0 -> Cons:Nil -> Cons:Nil 355.20/291.55 Cons :: S:0 -> Cons:Nil -> Cons:Nil 355.20/291.55 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 Nil :: Cons:Nil 355.20/291.55 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.55 part :: S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 part[Ite] :: True:False -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 gr :: S:0 -> S:0 -> True:False 355.20/291.55 notEmpty :: Cons:Nil -> True:False 355.20/291.55 True :: True:False 355.20/291.55 False :: True:False 355.20/291.55 lt :: S:0 -> S:0 -> True:False 355.20/291.55 S :: S:0 -> S:0 355.20/291.55 0 :: S:0 355.20/291.55 part[False][Ite] :: True:False -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 355.20/291.55 Rewrite Strategy: INNERMOST 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (9) CompletionProof (UPPER BOUND(ID)) 355.20/291.55 The transformation into a RNTS is sound, since: 355.20/291.55 355.20/291.55 (a) The obligation is a constructor system where every type has a constant constructor, 355.20/291.55 355.20/291.55 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 355.20/291.55 355.20/291.55 notEmpty_1 355.20/291.55 355.20/291.55 (c) The following functions are completely defined: 355.20/291.55 355.20/291.55 quicksort_1 355.20/291.55 part_4 355.20/291.55 app_2 355.20/291.55 qs_2 355.20/291.55 lt_2 355.20/291.55 gr_2 355.20/291.55 part[Ite]_5 355.20/291.55 part[False][Ite]_5 355.20/291.55 355.20/291.55 Due to the following rules being added: 355.20/291.55 355.20/291.55 lt(v0, v1) -> null_lt [0] 355.20/291.55 gr(v0, v1) -> null_gr [0] 355.20/291.55 part[Ite](v0, v1, v2, v3, v4) -> Nil [0] 355.20/291.55 part[False][Ite](v0, v1, v2, v3, v4) -> Nil [0] 355.20/291.55 qs(v0, v1) -> Nil [0] 355.20/291.55 355.20/291.55 And the following fresh constants: null_lt, null_gr 355.20/291.55 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (10) 355.20/291.55 Obligation: 355.20/291.55 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 355.20/291.55 355.20/291.55 Runtime Complexity Weighted TRS with Types. 355.20/291.55 The TRS R consists of the following rules: 355.20/291.55 355.20/291.55 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) [1] 355.20/291.55 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) [1] 355.20/291.55 quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1] 355.20/291.55 quicksort(Nil) -> Nil [1] 355.20/291.55 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](gr(x', x), x', Cons(x, xs), xs1, xs2) [1] 355.20/291.55 part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1] 355.20/291.55 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1] 355.20/291.55 app(Nil, ys) -> ys [1] 355.20/291.55 notEmpty(Cons(x, xs)) -> True [1] 355.20/291.55 notEmpty(Nil) -> False [1] 355.20/291.55 lt(S(x), S(y)) -> lt(x, y) [0] 355.20/291.55 lt(0, S(y)) -> True [0] 355.20/291.55 lt(x, 0) -> False [0] 355.20/291.55 gr(S(x), S(y)) -> gr(x, y) [0] 355.20/291.55 gr(0, y) -> False [0] 355.20/291.55 gr(S(x), 0) -> True [0] 355.20/291.55 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0] 355.20/291.55 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0] 355.20/291.55 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](lt(x', x), x', Cons(x, xs), xs1, xs2) [0] 355.20/291.55 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0] 355.20/291.55 lt(v0, v1) -> null_lt [0] 355.20/291.55 gr(v0, v1) -> null_gr [0] 355.20/291.55 part[Ite](v0, v1, v2, v3, v4) -> Nil [0] 355.20/291.55 part[False][Ite](v0, v1, v2, v3, v4) -> Nil [0] 355.20/291.55 qs(v0, v1) -> Nil [0] 355.20/291.55 355.20/291.55 The TRS has the following type information: 355.20/291.55 qs :: S:0 -> Cons:Nil -> Cons:Nil 355.20/291.55 Cons :: S:0 -> Cons:Nil -> Cons:Nil 355.20/291.55 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 Nil :: Cons:Nil 355.20/291.55 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.55 part :: S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 part[Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 gr :: S:0 -> S:0 -> True:False:null_lt:null_gr 355.20/291.55 notEmpty :: Cons:Nil -> True:False:null_lt:null_gr 355.20/291.55 True :: True:False:null_lt:null_gr 355.20/291.55 False :: True:False:null_lt:null_gr 355.20/291.55 lt :: S:0 -> S:0 -> True:False:null_lt:null_gr 355.20/291.55 S :: S:0 -> S:0 355.20/291.55 0 :: S:0 355.20/291.55 part[False][Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 null_lt :: True:False:null_lt:null_gr 355.20/291.55 null_gr :: True:False:null_lt:null_gr 355.20/291.55 355.20/291.55 Rewrite Strategy: INNERMOST 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (11) NarrowingProof (BOTH BOUNDS(ID, ID)) 355.20/291.55 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (12) 355.20/291.55 Obligation: 355.20/291.55 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 355.20/291.55 355.20/291.55 Runtime Complexity Weighted TRS with Types. 355.20/291.55 The TRS R consists of the following rules: 355.20/291.55 355.20/291.55 qs(x', Cons(x, Cons(x'', Cons(x''', xs')))) -> app(Cons(x, Nil), Cons(x', qs(x'', part(x'', Cons(x''', xs'), Nil, Nil)))) [2] 355.20/291.55 qs(x', Cons(x, Cons(x1, Nil))) -> app(Cons(x, Nil), Cons(x', Cons(x1, Nil))) [2] 355.20/291.55 qs(x', Cons(x, Nil)) -> app(Cons(x, Nil), Cons(x', Nil)) [2] 355.20/291.55 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part[Ite](gr(x, x'), x, Cons(x', xs), Nil, Nil)) [2] 355.20/291.55 quicksort(Cons(x, Nil)) -> Cons(x, Nil) [1] 355.20/291.55 quicksort(Nil) -> Nil [1] 355.20/291.55 part(S(x2), Cons(S(y'), xs), xs1, xs2) -> part[Ite](gr(x2, y'), S(x2), Cons(S(y'), xs), xs1, xs2) [1] 355.20/291.55 part(0, Cons(x, xs), xs1, xs2) -> part[Ite](False, 0, Cons(x, xs), xs1, xs2) [1] 355.20/291.55 part(S(x3), Cons(0, xs), xs1, xs2) -> part[Ite](True, S(x3), Cons(0, xs), xs1, xs2) [1] 355.20/291.55 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](null_gr, x', Cons(x, xs), xs1, xs2) [1] 355.20/291.55 part(x, Nil, xs1, xs2) -> app(xs1, xs2) [1] 355.20/291.55 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1] 355.20/291.55 app(Nil, ys) -> ys [1] 355.20/291.55 notEmpty(Cons(x, xs)) -> True [1] 355.20/291.55 notEmpty(Nil) -> False [1] 355.20/291.55 lt(S(x), S(y)) -> lt(x, y) [0] 355.20/291.55 lt(0, S(y)) -> True [0] 355.20/291.55 lt(x, 0) -> False [0] 355.20/291.55 gr(S(x), S(y)) -> gr(x, y) [0] 355.20/291.55 gr(0, y) -> False [0] 355.20/291.55 gr(S(x), 0) -> True [0] 355.20/291.55 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) [0] 355.20/291.55 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) [0] 355.20/291.55 part[Ite](False, S(x4), Cons(S(y''), xs), xs1, xs2) -> part[False][Ite](lt(x4, y''), S(x4), Cons(S(y''), xs), xs1, xs2) [0] 355.20/291.55 part[Ite](False, 0, Cons(S(y1), xs), xs1, xs2) -> part[False][Ite](True, 0, Cons(S(y1), xs), xs1, xs2) [0] 355.20/291.55 part[Ite](False, x', Cons(0, xs), xs1, xs2) -> part[False][Ite](False, x', Cons(0, xs), xs1, xs2) [0] 355.20/291.55 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](null_lt, x', Cons(x, xs), xs1, xs2) [0] 355.20/291.55 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) [0] 355.20/291.55 lt(v0, v1) -> null_lt [0] 355.20/291.55 gr(v0, v1) -> null_gr [0] 355.20/291.55 part[Ite](v0, v1, v2, v3, v4) -> Nil [0] 355.20/291.55 part[False][Ite](v0, v1, v2, v3, v4) -> Nil [0] 355.20/291.55 qs(v0, v1) -> Nil [0] 355.20/291.55 355.20/291.55 The TRS has the following type information: 355.20/291.55 qs :: S:0 -> Cons:Nil -> Cons:Nil 355.20/291.55 Cons :: S:0 -> Cons:Nil -> Cons:Nil 355.20/291.55 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 Nil :: Cons:Nil 355.20/291.55 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.55 part :: S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 part[Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 gr :: S:0 -> S:0 -> True:False:null_lt:null_gr 355.20/291.55 notEmpty :: Cons:Nil -> True:False:null_lt:null_gr 355.20/291.55 True :: True:False:null_lt:null_gr 355.20/291.55 False :: True:False:null_lt:null_gr 355.20/291.55 lt :: S:0 -> S:0 -> True:False:null_lt:null_gr 355.20/291.55 S :: S:0 -> S:0 355.20/291.55 0 :: S:0 355.20/291.55 part[False][Ite] :: True:False:null_lt:null_gr -> S:0 -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.55 null_lt :: True:False:null_lt:null_gr 355.20/291.55 null_gr :: True:False:null_lt:null_gr 355.20/291.55 355.20/291.55 Rewrite Strategy: INNERMOST 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 355.20/291.55 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 355.20/291.55 The constant constructors are abstracted as follows: 355.20/291.55 355.20/291.55 Nil => 0 355.20/291.55 True => 2 355.20/291.55 False => 1 355.20/291.55 0 => 0 355.20/291.55 null_lt => 0 355.20/291.55 null_gr => 0 355.20/291.55 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (14) 355.20/291.55 Obligation: 355.20/291.55 Complexity RNTS consisting of the following rules: 355.20/291.55 355.20/291.55 app(z, z') -{ 1 }-> ys :|: z' = ys, ys >= 0, z = 0 355.20/291.55 app(z, z') -{ 1 }-> 1 + x + app(xs, ys) :|: z = 1 + x + xs, xs >= 0, z' = ys, ys >= 0, x >= 0 355.20/291.55 gr(z, z') -{ 0 }-> gr(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 355.20/291.55 gr(z, z') -{ 0 }-> 2 :|: x >= 0, z = 1 + x, z' = 0 355.20/291.55 gr(z, z') -{ 0 }-> 1 :|: y >= 0, z = 0, z' = y 355.20/291.55 gr(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 355.20/291.55 lt(z, z') -{ 0 }-> lt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 355.20/291.55 lt(z, z') -{ 0 }-> 2 :|: z' = 1 + y, y >= 0, z = 0 355.20/291.55 lt(z, z') -{ 0 }-> 1 :|: x >= 0, z = x, z' = 0 355.20/291.55 lt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 355.20/291.55 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.55 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(x2, y'), 1 + x2, 1 + (1 + y') + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + (1 + y') + xs, z1 = xs2, z = 1 + x2, y' >= 0, z'' = xs1, xs1 >= 0, x2 >= 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + x3, 1 + 0 + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + 0 + xs, z1 = xs2, z'' = xs1, xs1 >= 0, z = 1 + x3, x3 >= 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + x + xs, z1 = xs2, x >= 0, z'' = xs1, xs1 >= 0, z = 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, x', 1 + x + xs, xs1, xs2) :|: xs >= 0, xs2 >= 0, z' = 1 + x + xs, z1 = xs2, x' >= 0, x >= 0, z'' = xs1, xs1 >= 0, z = x' 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> app(xs1, xs2) :|: xs2 >= 0, z1 = xs2, x >= 0, z'' = xs1, xs1 >= 0, z = x, z' = 0 355.20/291.55 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(x', xs, xs1, xs2) :|: z' = x', xs >= 0, xs2 >= 0, z = 1, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(x', xs, xs1, 1 + x + xs2) :|: z = 2, z' = x', xs >= 0, xs2 >= 0, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(x4, y''), 1 + x4, 1 + (1 + y'') + xs, xs1, xs2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, x4 >= 0, xs2 >= 0, z = 1, z2 = xs2, z' = 1 + x4, y'' >= 0, z1 = xs1, xs1 >= 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, xs1, xs2) :|: y1 >= 0, xs >= 0, xs2 >= 0, z = 1, z2 = xs2, z'' = 1 + (1 + y1) + xs, z1 = xs1, xs1 >= 0, z' = 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, x', 1 + 0 + xs, xs1, xs2) :|: z' = x', xs >= 0, xs2 >= 0, z'' = 1 + 0 + xs, z = 1, z2 = xs2, x' >= 0, z1 = xs1, xs1 >= 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, x', 1 + x + xs, xs1, xs2) :|: z' = x', xs >= 0, xs2 >= 0, z = 1, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(x', xs, 1 + x + xs1, xs2) :|: z = 2, z' = x', xs >= 0, xs2 >= 0, z2 = xs2, x' >= 0, x >= 0, z1 = xs1, xs1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, v4 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, z2 = v4, v2 >= 0, v3 >= 0 355.20/291.55 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + x' + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: x' >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0, z = x' 355.20/291.55 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + x' + 0) :|: x' >= 0, x >= 0, z' = 1 + x + 0, z = x' 355.20/291.55 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + x' + (1 + x1 + 0)) :|: x1 >= 0, x' >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0), z = x' 355.20/291.55 qs(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 355.20/291.55 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.55 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.55 quicksort(z) -{ 1 }-> 1 + x + 0 :|: x >= 0, z = 1 + x + 0 355.20/291.55 355.20/291.55 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (15) SimplificationProof (BOTH BOUNDS(ID, ID)) 355.20/291.55 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (16) 355.20/291.55 Obligation: 355.20/291.55 Complexity RNTS consisting of the following rules: 355.20/291.55 355.20/291.55 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.55 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.55 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.55 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.55 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.55 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.55 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.55 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.55 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.55 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.55 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.55 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.55 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.55 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.55 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.55 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.55 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.55 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.55 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.55 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.55 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.55 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.55 355.20/291.55 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 355.20/291.55 Found the following analysis order by SCC decomposition: 355.20/291.55 355.20/291.55 { notEmpty } 355.20/291.55 { gr } 355.20/291.55 { lt } 355.20/291.55 { app } 355.20/291.55 { part, part[False][Ite], part[Ite] } 355.20/291.55 { qs } 355.20/291.55 { quicksort } 355.20/291.55 355.20/291.55 ---------------------------------------- 355.20/291.55 355.20/291.55 (18) 355.20/291.55 Obligation: 355.20/291.55 Complexity RNTS consisting of the following rules: 355.20/291.55 355.20/291.55 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.55 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.55 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.55 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.55 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.55 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.55 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {notEmpty}, {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (19) ResultPropagationProof (UPPER BOUND(ID)) 355.20/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (20) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {notEmpty}, {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (21) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed SIZE bound using CoFloCo for: notEmpty 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(1) with polynomial bound: 2 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (22) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {notEmpty}, {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: ?, size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (23) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: notEmpty 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(1) with polynomial bound: 1 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (24) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (25) ResultPropagationProof (UPPER BOUND(ID)) 355.20/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (26) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (27) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed SIZE bound using CoFloCo for: gr 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(1) with polynomial bound: 2 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (28) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {gr}, {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: ?, size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (29) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: gr 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(1) with polynomial bound: 0 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (30) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](gr(z - 1, y'), 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](gr(x, x'), x, 1 + x' + xs, 0, 0)) :|: xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (31) ResultPropagationProof (UPPER BOUND(ID)) 355.20/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (32) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (33) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed SIZE bound using CoFloCo for: lt 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(1) with polynomial bound: 2 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (34) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {lt}, {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: ?, size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (35) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: lt 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(1) with polynomial bound: 0 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (36) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> lt(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](lt(z' - 1, y''), 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (37) ResultPropagationProof (UPPER BOUND(ID)) 355.20/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (38) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (39) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed SIZE bound using CoFloCo for: app 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: z + z' 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (40) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {app}, {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: ?, size: O(n^1) [z + z'] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (41) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: app 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: 1 + z 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (42) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 1 }-> 1 + x + app(xs, z') :|: z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> app(z'', z1) :|: z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + (1 + x1 + 0)) :|: x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + (z' - 1) + 0, 1 + z + 0) :|: z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (43) ResultPropagationProof (UPPER BOUND(ID)) 355.20/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (44) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (45) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed SIZE bound using KoAT for: part 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: z' + z'' + z1 355.20/291.56 355.20/291.56 Computed SIZE bound using KoAT for: part[False][Ite] 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: z'' + z1 + z2 355.20/291.56 355.20/291.56 Computed SIZE bound using CoFloCo for: part[Ite] 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: z'' + z1 + z2 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (46) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {part,part[False][Ite],part[Ite]}, {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: ?, size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: ?, size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: ?, size: O(n^1) [z'' + z1 + z2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (47) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: part 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: 2 + 2*z' + z'' 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: part[False][Ite] 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: 2*z'' + z1 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: part[Ite] 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: 1 + 2*z'' + z1 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (48) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](s', 1 + (z - 1), 1 + (1 + y') + xs, z'', z1) :|: s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](2, 1 + (z - 1), 1 + 0 + (z' - 1), z'', z1) :|: z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](1, 0, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 1 }-> part[Ite](0, z, 1 + x + xs, z'', z1) :|: xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, z1, 1 + x + z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](s2, 1 + (z' - 1), 1 + (1 + y'') + xs, z1, z2) :|: s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](2, 0, 1 + (1 + y1) + xs, z1, z2) :|: y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](1, z', 1 + 0 + (z'' - 1), z1, z2) :|: z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part[False][Ite](0, z', 1 + x + xs, z1, z2) :|: xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> part(z', xs, 1 + x + z1, z2) :|: z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 2 }-> app(1 + x + 0, 1 + z + qs(x'', part(x'', 1 + x''' + xs', 0, 0))) :|: z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 2 }-> qs(x, part[Ite](s, x, 1 + x' + xs, 0, 0)) :|: s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (49) ResultPropagationProof (UPPER BOUND(ID)) 355.20/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (50) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 6 + 2*x''' + 2*xs' }-> app(1 + x + 0, 1 + z + qs(x'', s7)) :|: s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 5 + 2*x' + 2*xs }-> qs(x, s8) :|: s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (51) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed SIZE bound using CoFloCo for: qs 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: 1 + z + z' 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (52) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 6 + 2*x''' + 2*xs' }-> app(1 + x + 0, 1 + z + qs(x'', s7)) :|: s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 5 + 2*x' + 2*xs }-> qs(x, s8) :|: s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {qs}, {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 qs: runtime: ?, size: O(n^1) [1 + z + z'] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (53) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed RUNTIME bound using CoFloCo for: qs 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^2) with polynomial bound: 6 + 8*z' + 2*z'^2 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (54) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 6 + 2*x''' + 2*xs' }-> app(1 + x + 0, 1 + z + qs(x'', s7)) :|: s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 5 + 2*x' + 2*xs }-> qs(x, s8) :|: s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z'] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (55) ResultPropagationProof (UPPER BOUND(ID)) 355.20/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (56) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 14 + 8*s7 + 2*s7^2 + x + 2*x''' + 2*xs' }-> s21 :|: s20 >= 0, s20 <= x'' + s7 + 1, s21 >= 0, s21 <= 1 + x + 0 + (1 + z + s20), s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 11 + 8*s8 + 2*s8^2 + 2*x' + 2*xs }-> s22 :|: s22 >= 0, s22 <= x + s8 + 1, s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z'] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (57) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed SIZE bound using CoFloCo for: quicksort 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^1) with polynomial bound: z 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (58) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 14 + 8*s7 + 2*s7^2 + x + 2*x''' + 2*xs' }-> s21 :|: s20 >= 0, s20 <= x'' + s7 + 1, s21 >= 0, s21 <= 1 + x + 0 + (1 + z + s20), s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 11 + 8*s8 + 2*s8^2 + 2*x' + 2*xs }-> s22 :|: s22 >= 0, s22 <= x + s8 + 1, s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: {quicksort} 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z'] 355.20/291.56 quicksort: runtime: ?, size: O(n^1) [z] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (59) IntTrsBoundProof (UPPER BOUND(ID)) 355.20/291.56 355.20/291.56 Computed RUNTIME bound using KoAT for: quicksort 355.20/291.56 after applying outer abstraction to obtain an ITS, 355.20/291.56 resulting in: O(n^2) with polynomial bound: 23 + 28*z + 8*z^2 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (60) 355.20/291.56 Obligation: 355.20/291.56 Complexity RNTS consisting of the following rules: 355.20/291.56 355.20/291.56 app(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 355.20/291.56 app(z, z') -{ 2 + xs }-> 1 + x + s6 :|: s6 >= 0, s6 <= xs + z', z = 1 + x + xs, xs >= 0, z' >= 0, x >= 0 355.20/291.56 gr(z, z') -{ 0 }-> s'' :|: s'' >= 0, s'' <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 gr(z, z') -{ 0 }-> 2 :|: z - 1 >= 0, z' = 0 355.20/291.56 gr(z, z') -{ 0 }-> 1 :|: z' >= 0, z = 0 355.20/291.56 gr(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 lt(z, z') -{ 0 }-> s1 :|: s1 >= 0, s1 <= 2, z - 1 >= 0, z' - 1 >= 0 355.20/291.56 lt(z, z') -{ 0 }-> 2 :|: z' - 1 >= 0, z = 0 355.20/291.56 lt(z, z') -{ 0 }-> 1 :|: z >= 0, z' = 0 355.20/291.56 lt(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 355.20/291.56 notEmpty(z) -{ 1 }-> 1 :|: z = 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s10 :|: s10 >= 0, s10 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, x >= 0, z'' >= 0, z = 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + 2*z' + z'' }-> s11 :|: s11 >= 0, s11 <= 1 + 0 + (z' - 1) + z'' + z1, z' - 1 >= 0, z1 >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part(z, z', z'', z1) -{ 4 + 2*x + 2*xs + z'' }-> s12 :|: s12 >= 0, s12 <= 1 + x + xs + z'' + z1, xs >= 0, z1 >= 0, z' = 1 + x + xs, z >= 0, x >= 0, z'' >= 0 355.20/291.56 part(z, z', z'', z1) -{ 2 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + z1, z1 >= 0, z >= 0, z'' >= 0, z' = 0 355.20/291.56 part(z, z', z'', z1) -{ 6 + 2*xs + 2*y' + z'' }-> s9 :|: s9 >= 0, s9 <= 1 + (1 + y') + xs + z'' + z1, s' >= 0, s' <= 2, xs >= 0, z1 >= 0, z' = 1 + (1 + y') + xs, y' >= 0, z'' >= 0, z - 1 >= 0 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s14 :|: s14 >= 0, s14 <= xs + z1 + (1 + x + z2), z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 2 + 2*xs + z1 }-> s19 :|: s19 >= 0, s19 <= xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[False][Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 3 + x + 2*xs + z1 }-> s13 :|: s13 >= 0, s13 <= xs + (1 + x + z1) + z2, z = 2, xs >= 0, z2 >= 0, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y'' + z1 }-> s15 :|: s15 >= 0, s15 <= 1 + (1 + y'') + xs + z1 + z2, s2 >= 0, s2 <= 2, z'' = 1 + (1 + y'') + xs, xs >= 0, z' - 1 >= 0, z2 >= 0, z = 1, y'' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 4 + 2*xs + 2*y1 + z1 }-> s16 :|: s16 >= 0, s16 <= 1 + (1 + y1) + xs + z1 + z2, y1 >= 0, xs >= 0, z2 >= 0, z = 1, z'' = 1 + (1 + y1) + xs, z1 >= 0, z' = 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2*z'' + z1 }-> s17 :|: s17 >= 0, s17 <= 1 + 0 + (z'' - 1) + z1 + z2, z'' - 1 >= 0, z2 >= 0, z = 1, z' >= 0, z1 >= 0 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 2 + 2*x + 2*xs + z1 }-> s18 :|: s18 >= 0, s18 <= 1 + x + xs + z1 + z2, xs >= 0, z2 >= 0, z = 1, z' >= 0, x >= 0, z1 >= 0, z'' = 1 + x + xs 355.20/291.56 part[Ite](z, z', z'', z1, z2) -{ 0 }-> 0 :|: z >= 0, z2 >= 0, z' >= 0, z'' >= 0, z1 >= 0 355.20/291.56 qs(z, z') -{ 14 + 8*s7 + 2*s7^2 + x + 2*x''' + 2*xs' }-> s21 :|: s20 >= 0, s20 <= x'' + s7 + 1, s21 >= 0, s21 <= 1 + x + 0 + (1 + z + s20), s7 >= 0, s7 <= 1 + x''' + xs' + 0 + 0, z >= 0, x >= 0, xs' >= 0, z' = 1 + x + (1 + x'' + (1 + x''' + xs')), x''' >= 0, x'' >= 0 355.20/291.56 qs(z, z') -{ 4 + x }-> s3 :|: s3 >= 0, s3 <= 1 + x + 0 + (1 + z + (1 + x1 + 0)), x1 >= 0, z >= 0, x >= 0, z' = 1 + x + (1 + x1 + 0) 355.20/291.56 qs(z, z') -{ 3 + z' }-> s4 :|: s4 >= 0, s4 <= 1 + (z' - 1) + 0 + (1 + z + 0), z >= 0, z' - 1 >= 0 355.20/291.56 qs(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 355.20/291.56 quicksort(z) -{ 11 + 8*s8 + 2*s8^2 + 2*x' + 2*xs }-> s22 :|: s22 >= 0, s22 <= x + s8 + 1, s8 >= 0, s8 <= 1 + x' + xs + 0 + 0, s >= 0, s <= 2, xs >= 0, x >= 0, x' >= 0, z = 1 + x + (1 + x' + xs) 355.20/291.56 quicksort(z) -{ 1 }-> 0 :|: z = 0 355.20/291.56 quicksort(z) -{ 1 }-> 1 + (z - 1) + 0 :|: z - 1 >= 0 355.20/291.56 355.20/291.56 Function symbols to be analyzed: 355.20/291.56 Previous analysis results are: 355.20/291.56 notEmpty: runtime: O(1) [1], size: O(1) [2] 355.20/291.56 gr: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 lt: runtime: O(1) [0], size: O(1) [2] 355.20/291.56 app: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 355.20/291.56 part: runtime: O(n^1) [2 + 2*z' + z''], size: O(n^1) [z' + z'' + z1] 355.20/291.56 part[False][Ite]: runtime: O(n^1) [2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 part[Ite]: runtime: O(n^1) [1 + 2*z'' + z1], size: O(n^1) [z'' + z1 + z2] 355.20/291.56 qs: runtime: O(n^2) [6 + 8*z' + 2*z'^2], size: O(n^1) [1 + z + z'] 355.20/291.56 quicksort: runtime: O(n^2) [23 + 28*z + 8*z^2], size: O(n^1) [z] 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (61) FinalProof (FINISHED) 355.20/291.56 Computed overall runtime complexity 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (62) 355.20/291.56 BOUNDS(1, n^2) 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (63) RenamingProof (BOTH BOUNDS(ID, ID)) 355.20/291.56 Renamed function symbols to avoid clashes with predefined symbol. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (64) 355.20/291.56 Obligation: 355.20/291.56 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 355.20/291.56 355.20/291.56 355.20/291.56 The TRS R consists of the following rules: 355.20/291.56 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 355.20/291.56 The (relative) TRS S consists of the following rules: 355.20/291.56 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Rewrite Strategy: INNERMOST 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (65) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 355.20/291.56 Infered types. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (66) 355.20/291.56 Obligation: 355.20/291.56 Innermost TRS: 355.20/291.56 Rules: 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Types: 355.20/291.56 qs :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 Cons :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 Nil :: Cons:Nil 355.20/291.56 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.56 part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 > :: S:0' -> S:0' -> True:False 355.20/291.56 notEmpty :: Cons:Nil -> True:False 355.20/291.56 True :: True:False 355.20/291.56 False :: True:False 355.20/291.56 < :: S:0' -> S:0' -> True:False 355.20/291.56 S :: S:0' -> S:0' 355.20/291.56 0' :: S:0' 355.20/291.56 part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 hole_Cons:Nil1_0 :: Cons:Nil 355.20/291.56 hole_S:0'2_0 :: S:0' 355.20/291.56 hole_True:False3_0 :: True:False 355.20/291.56 gen_Cons:Nil4_0 :: Nat -> Cons:Nil 355.20/291.56 gen_S:0'5_0 :: Nat -> S:0' 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (67) OrderProof (LOWER BOUND(ID)) 355.20/291.56 Heuristically decided to analyse the following defined symbols: 355.20/291.56 app, quicksort, part, >, < 355.20/291.56 355.20/291.56 They will be analysed ascendingly in the following order: 355.20/291.56 app < quicksort 355.20/291.56 app < part 355.20/291.56 part < quicksort 355.20/291.56 > < part 355.20/291.56 < < part 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (68) 355.20/291.56 Obligation: 355.20/291.56 Innermost TRS: 355.20/291.56 Rules: 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Types: 355.20/291.56 qs :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 Cons :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 Nil :: Cons:Nil 355.20/291.56 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.56 part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 > :: S:0' -> S:0' -> True:False 355.20/291.56 notEmpty :: Cons:Nil -> True:False 355.20/291.56 True :: True:False 355.20/291.56 False :: True:False 355.20/291.56 < :: S:0' -> S:0' -> True:False 355.20/291.56 S :: S:0' -> S:0' 355.20/291.56 0' :: S:0' 355.20/291.56 part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 hole_Cons:Nil1_0 :: Cons:Nil 355.20/291.56 hole_S:0'2_0 :: S:0' 355.20/291.56 hole_True:False3_0 :: True:False 355.20/291.56 gen_Cons:Nil4_0 :: Nat -> Cons:Nil 355.20/291.56 gen_S:0'5_0 :: Nat -> S:0' 355.20/291.56 355.20/291.56 355.20/291.56 Generator Equations: 355.20/291.56 gen_Cons:Nil4_0(0) <=> Nil 355.20/291.56 gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x)) 355.20/291.56 gen_S:0'5_0(0) <=> 0' 355.20/291.56 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 355.20/291.56 355.20/291.56 355.20/291.56 The following defined symbols remain to be analysed: 355.20/291.56 app, quicksort, part, >, < 355.20/291.56 355.20/291.56 They will be analysed ascendingly in the following order: 355.20/291.56 app < quicksort 355.20/291.56 app < part 355.20/291.56 part < quicksort 355.20/291.56 > < part 355.20/291.56 < < part 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (69) RewriteLemmaProof (LOWER BOUND(ID)) 355.20/291.56 Proved the following rewrite lemma: 355.20/291.56 app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 355.20/291.56 355.20/291.56 Induction Base: 355.20/291.56 app(gen_Cons:Nil4_0(0), gen_Cons:Nil4_0(b)) ->_R^Omega(1) 355.20/291.56 gen_Cons:Nil4_0(b) 355.20/291.56 355.20/291.56 Induction Step: 355.20/291.56 app(gen_Cons:Nil4_0(+(n7_0, 1)), gen_Cons:Nil4_0(b)) ->_R^Omega(1) 355.20/291.56 Cons(0', app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b))) ->_IH 355.20/291.56 Cons(0', gen_Cons:Nil4_0(+(b, c8_0))) 355.20/291.56 355.20/291.56 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (70) 355.20/291.56 Complex Obligation (BEST) 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (71) 355.20/291.56 Obligation: 355.20/291.56 Proved the lower bound n^1 for the following obligation: 355.20/291.56 355.20/291.56 Innermost TRS: 355.20/291.56 Rules: 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Types: 355.20/291.56 qs :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 Cons :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 Nil :: Cons:Nil 355.20/291.56 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.56 part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 > :: S:0' -> S:0' -> True:False 355.20/291.56 notEmpty :: Cons:Nil -> True:False 355.20/291.56 True :: True:False 355.20/291.56 False :: True:False 355.20/291.56 < :: S:0' -> S:0' -> True:False 355.20/291.56 S :: S:0' -> S:0' 355.20/291.56 0' :: S:0' 355.20/291.56 part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 hole_Cons:Nil1_0 :: Cons:Nil 355.20/291.56 hole_S:0'2_0 :: S:0' 355.20/291.56 hole_True:False3_0 :: True:False 355.20/291.56 gen_Cons:Nil4_0 :: Nat -> Cons:Nil 355.20/291.56 gen_S:0'5_0 :: Nat -> S:0' 355.20/291.56 355.20/291.56 355.20/291.56 Generator Equations: 355.20/291.56 gen_Cons:Nil4_0(0) <=> Nil 355.20/291.56 gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x)) 355.20/291.56 gen_S:0'5_0(0) <=> 0' 355.20/291.56 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 355.20/291.56 355.20/291.56 355.20/291.56 The following defined symbols remain to be analysed: 355.20/291.56 app, quicksort, part, >, < 355.20/291.56 355.20/291.56 They will be analysed ascendingly in the following order: 355.20/291.56 app < quicksort 355.20/291.56 app < part 355.20/291.56 part < quicksort 355.20/291.56 > < part 355.20/291.56 < < part 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (72) LowerBoundPropagationProof (FINISHED) 355.20/291.56 Propagated lower bound. 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (73) 355.20/291.56 BOUNDS(n^1, INF) 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (74) 355.20/291.56 Obligation: 355.20/291.56 Innermost TRS: 355.20/291.56 Rules: 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Types: 355.20/291.56 qs :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 Cons :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 Nil :: Cons:Nil 355.20/291.56 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.56 part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 > :: S:0' -> S:0' -> True:False 355.20/291.56 notEmpty :: Cons:Nil -> True:False 355.20/291.56 True :: True:False 355.20/291.56 False :: True:False 355.20/291.56 < :: S:0' -> S:0' -> True:False 355.20/291.56 S :: S:0' -> S:0' 355.20/291.56 0' :: S:0' 355.20/291.56 part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 hole_Cons:Nil1_0 :: Cons:Nil 355.20/291.56 hole_S:0'2_0 :: S:0' 355.20/291.56 hole_True:False3_0 :: True:False 355.20/291.56 gen_Cons:Nil4_0 :: Nat -> Cons:Nil 355.20/291.56 gen_S:0'5_0 :: Nat -> S:0' 355.20/291.56 355.20/291.56 355.20/291.56 Lemmas: 355.20/291.56 app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 355.20/291.56 355.20/291.56 355.20/291.56 Generator Equations: 355.20/291.56 gen_Cons:Nil4_0(0) <=> Nil 355.20/291.56 gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x)) 355.20/291.56 gen_S:0'5_0(0) <=> 0' 355.20/291.56 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 355.20/291.56 355.20/291.56 355.20/291.56 The following defined symbols remain to be analysed: 355.20/291.56 >, quicksort, part, < 355.20/291.56 355.20/291.56 They will be analysed ascendingly in the following order: 355.20/291.56 part < quicksort 355.20/291.56 > < part 355.20/291.56 < < part 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (75) RewriteLemmaProof (LOWER BOUND(ID)) 355.20/291.56 Proved the following rewrite lemma: 355.20/291.56 >(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0) 355.20/291.56 355.20/291.56 Induction Base: 355.20/291.56 >(gen_S:0'5_0(0), gen_S:0'5_0(0)) ->_R^Omega(0) 355.20/291.56 False 355.20/291.56 355.20/291.56 Induction Step: 355.20/291.56 >(gen_S:0'5_0(+(n892_0, 1)), gen_S:0'5_0(+(n892_0, 1))) ->_R^Omega(0) 355.20/291.56 >(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) ->_IH 355.20/291.56 False 355.20/291.56 355.20/291.56 We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (76) 355.20/291.56 Obligation: 355.20/291.56 Innermost TRS: 355.20/291.56 Rules: 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Types: 355.20/291.56 qs :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 Cons :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 Nil :: Cons:Nil 355.20/291.56 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.56 part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 > :: S:0' -> S:0' -> True:False 355.20/291.56 notEmpty :: Cons:Nil -> True:False 355.20/291.56 True :: True:False 355.20/291.56 False :: True:False 355.20/291.56 < :: S:0' -> S:0' -> True:False 355.20/291.56 S :: S:0' -> S:0' 355.20/291.56 0' :: S:0' 355.20/291.56 part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 hole_Cons:Nil1_0 :: Cons:Nil 355.20/291.56 hole_S:0'2_0 :: S:0' 355.20/291.56 hole_True:False3_0 :: True:False 355.20/291.56 gen_Cons:Nil4_0 :: Nat -> Cons:Nil 355.20/291.56 gen_S:0'5_0 :: Nat -> S:0' 355.20/291.56 355.20/291.56 355.20/291.56 Lemmas: 355.20/291.56 app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 355.20/291.56 >(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0) 355.20/291.56 355.20/291.56 355.20/291.56 Generator Equations: 355.20/291.56 gen_Cons:Nil4_0(0) <=> Nil 355.20/291.56 gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x)) 355.20/291.56 gen_S:0'5_0(0) <=> 0' 355.20/291.56 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 355.20/291.56 355.20/291.56 355.20/291.56 The following defined symbols remain to be analysed: 355.20/291.56 <, quicksort, part 355.20/291.56 355.20/291.56 They will be analysed ascendingly in the following order: 355.20/291.56 part < quicksort 355.20/291.56 < < part 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (77) RewriteLemmaProof (LOWER BOUND(ID)) 355.20/291.56 Proved the following rewrite lemma: 355.20/291.56 <(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) -> True, rt in Omega(0) 355.20/291.56 355.20/291.56 Induction Base: 355.20/291.56 <(gen_S:0'5_0(0), gen_S:0'5_0(+(1, 0))) ->_R^Omega(0) 355.20/291.56 True 355.20/291.56 355.20/291.56 Induction Step: 355.20/291.56 <(gen_S:0'5_0(+(n1173_0, 1)), gen_S:0'5_0(+(1, +(n1173_0, 1)))) ->_R^Omega(0) 355.20/291.56 <(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) ->_IH 355.20/291.56 True 355.20/291.56 355.20/291.56 We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (78) 355.20/291.56 Obligation: 355.20/291.56 Innermost TRS: 355.20/291.56 Rules: 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Types: 355.20/291.56 qs :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 Cons :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 Nil :: Cons:Nil 355.20/291.56 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.56 part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 > :: S:0' -> S:0' -> True:False 355.20/291.56 notEmpty :: Cons:Nil -> True:False 355.20/291.56 True :: True:False 355.20/291.56 False :: True:False 355.20/291.56 < :: S:0' -> S:0' -> True:False 355.20/291.56 S :: S:0' -> S:0' 355.20/291.56 0' :: S:0' 355.20/291.56 part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 hole_Cons:Nil1_0 :: Cons:Nil 355.20/291.56 hole_S:0'2_0 :: S:0' 355.20/291.56 hole_True:False3_0 :: True:False 355.20/291.56 gen_Cons:Nil4_0 :: Nat -> Cons:Nil 355.20/291.56 gen_S:0'5_0 :: Nat -> S:0' 355.20/291.56 355.20/291.56 355.20/291.56 Lemmas: 355.20/291.56 app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 355.20/291.56 >(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0) 355.20/291.56 <(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) -> True, rt in Omega(0) 355.20/291.56 355.20/291.56 355.20/291.56 Generator Equations: 355.20/291.56 gen_Cons:Nil4_0(0) <=> Nil 355.20/291.56 gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x)) 355.20/291.56 gen_S:0'5_0(0) <=> 0' 355.20/291.56 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 355.20/291.56 355.20/291.56 355.20/291.56 The following defined symbols remain to be analysed: 355.20/291.56 part, quicksort 355.20/291.56 355.20/291.56 They will be analysed ascendingly in the following order: 355.20/291.56 part < quicksort 355.20/291.56 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (79) RewriteLemmaProof (LOWER BOUND(ID)) 355.20/291.56 Proved the following rewrite lemma: 355.20/291.56 part(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1459_0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) -> gen_Cons:Nil4_0(+(c, d)), rt in Omega(1 + c + n1459_0) 355.20/291.56 355.20/291.56 Induction Base: 355.20/291.56 part(gen_S:0'5_0(0), gen_Cons:Nil4_0(0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(1) 355.20/291.56 app(gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_L^Omega(1 + c) 355.20/291.56 gen_Cons:Nil4_0(+(c, d)) 355.20/291.56 355.20/291.56 Induction Step: 355.20/291.56 part(gen_S:0'5_0(0), gen_Cons:Nil4_0(+(n1459_0, 1)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(1) 355.20/291.56 part[Ite](>(gen_S:0'5_0(0), 0'), gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_L^Omega(0) 355.20/291.56 part[Ite](False, gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(0) 355.20/291.56 part[False][Ite](<(gen_S:0'5_0(0), 0'), gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(0) 355.20/291.56 part[False][Ite](False, gen_S:0'5_0(0), Cons(0', gen_Cons:Nil4_0(n1459_0)), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_R^Omega(0) 355.20/291.56 part(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1459_0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) ->_IH 355.20/291.56 gen_Cons:Nil4_0(+(c, d)) 355.20/291.56 355.20/291.56 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 355.20/291.56 ---------------------------------------- 355.20/291.56 355.20/291.56 (80) 355.20/291.56 Obligation: 355.20/291.56 Innermost TRS: 355.20/291.56 Rules: 355.20/291.56 qs(x', Cons(x, xs)) -> app(Cons(x, Nil), Cons(x', quicksort(xs))) 355.20/291.56 quicksort(Cons(x, Cons(x', xs))) -> qs(x, part(x, Cons(x', xs), Nil, Nil)) 355.20/291.56 quicksort(Cons(x, Nil)) -> Cons(x, Nil) 355.20/291.56 quicksort(Nil) -> Nil 355.20/291.56 part(x', Cons(x, xs), xs1, xs2) -> part[Ite](>(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part(x, Nil, xs1, xs2) -> app(xs1, xs2) 355.20/291.56 app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) 355.20/291.56 app(Nil, ys) -> ys 355.20/291.56 notEmpty(Cons(x, xs)) -> True 355.20/291.56 notEmpty(Nil) -> False 355.20/291.56 <(S(x), S(y)) -> <(x, y) 355.20/291.56 <(0', S(y)) -> True 355.20/291.56 <(x, 0') -> False 355.20/291.56 >(S(x), S(y)) -> >(x, y) 355.20/291.56 >(0', y) -> False 355.20/291.56 >(S(x), 0') -> True 355.20/291.56 part[Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, Cons(x, xs1), xs2) 355.20/291.56 part[False][Ite](True, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, Cons(x, xs2)) 355.20/291.56 part[Ite](False, x', Cons(x, xs), xs1, xs2) -> part[False][Ite](<(x', x), x', Cons(x, xs), xs1, xs2) 355.20/291.56 part[False][Ite](False, x', Cons(x, xs), xs1, xs2) -> part(x', xs, xs1, xs2) 355.20/291.56 355.20/291.56 Types: 355.20/291.56 qs :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 Cons :: S:0' -> Cons:Nil -> Cons:Nil 355.20/291.56 app :: Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.56 Nil :: Cons:Nil 355.20/291.56 quicksort :: Cons:Nil -> Cons:Nil 355.20/291.57 part :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.57 part[Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.57 > :: S:0' -> S:0' -> True:False 355.20/291.57 notEmpty :: Cons:Nil -> True:False 355.20/291.57 True :: True:False 355.20/291.57 False :: True:False 355.20/291.57 < :: S:0' -> S:0' -> True:False 355.20/291.57 S :: S:0' -> S:0' 355.20/291.57 0' :: S:0' 355.20/291.57 part[False][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil -> Cons:Nil 355.20/291.57 hole_Cons:Nil1_0 :: Cons:Nil 355.20/291.57 hole_S:0'2_0 :: S:0' 355.20/291.57 hole_True:False3_0 :: True:False 355.20/291.57 gen_Cons:Nil4_0 :: Nat -> Cons:Nil 355.20/291.57 gen_S:0'5_0 :: Nat -> S:0' 355.20/291.57 355.20/291.57 355.20/291.57 Lemmas: 355.20/291.57 app(gen_Cons:Nil4_0(n7_0), gen_Cons:Nil4_0(b)) -> gen_Cons:Nil4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 355.20/291.57 >(gen_S:0'5_0(n892_0), gen_S:0'5_0(n892_0)) -> False, rt in Omega(0) 355.20/291.57 <(gen_S:0'5_0(n1173_0), gen_S:0'5_0(+(1, n1173_0))) -> True, rt in Omega(0) 355.20/291.57 part(gen_S:0'5_0(0), gen_Cons:Nil4_0(n1459_0), gen_Cons:Nil4_0(c), gen_Cons:Nil4_0(d)) -> gen_Cons:Nil4_0(+(c, d)), rt in Omega(1 + c + n1459_0) 355.20/291.57 355.20/291.57 355.20/291.57 Generator Equations: 355.20/291.57 gen_Cons:Nil4_0(0) <=> Nil 355.20/291.57 gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x)) 355.20/291.57 gen_S:0'5_0(0) <=> 0' 355.20/291.57 gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x)) 355.20/291.57 355.20/291.57 355.20/291.57 The following defined symbols remain to be analysed: 355.20/291.57 quicksort 355.20/291.59 EOF