1117.84/291.50 WORST_CASE(Omega(n^2), ?) 1132.45/295.17 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1132.45/295.17 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1132.45/295.17 1132.45/295.17 1132.45/295.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1132.45/295.17 1132.45/295.17 (0) CpxTRS 1132.45/295.17 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1132.45/295.17 (2) CpxTRS 1132.45/295.17 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1132.45/295.17 (4) typed CpxTrs 1132.45/295.17 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1132.45/295.17 (6) typed CpxTrs 1132.45/295.17 (7) RewriteLemmaProof [LOWER BOUND(ID), 285 ms] 1132.45/295.17 (8) BEST 1132.45/295.17 (9) proven lower bound 1132.45/295.17 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1132.45/295.17 (11) BOUNDS(n^1, INF) 1132.45/295.17 (12) typed CpxTrs 1132.45/295.17 (13) RewriteLemmaProof [LOWER BOUND(ID), 73 ms] 1132.45/295.17 (14) typed CpxTrs 1132.45/295.17 (15) RewriteLemmaProof [LOWER BOUND(ID), 77 ms] 1132.45/295.17 (16) typed CpxTrs 1132.45/295.17 (17) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 1132.45/295.17 (18) typed CpxTrs 1132.45/295.17 (19) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 1132.45/295.17 (20) typed CpxTrs 1132.45/295.17 (21) RewriteLemmaProof [LOWER BOUND(ID), 63 ms] 1132.45/295.17 (22) proven lower bound 1132.45/295.17 (23) LowerBoundPropagationProof [FINISHED, 0 ms] 1132.45/295.17 (24) BOUNDS(n^2, INF) 1132.45/295.17 1132.45/295.17 1132.45/295.17 ---------------------------------------- 1132.45/295.17 1132.45/295.17 (0) 1132.45/295.17 Obligation: 1132.45/295.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1132.45/295.17 1132.45/295.17 1132.45/295.17 The TRS R consists of the following rules: 1132.45/295.17 1132.45/295.17 minus(x, 0) -> x 1132.45/295.17 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.17 quot(0, s(y)) -> 0 1132.45/295.17 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.17 le(0, y) -> true 1132.45/295.17 le(s(x), 0) -> false 1132.45/295.17 le(s(x), s(y)) -> le(x, y) 1132.45/295.17 app(nil, y) -> y 1132.45/295.17 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.17 low(n, nil) -> nil 1132.45/295.17 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.17 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.17 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.17 high(n, nil) -> nil 1132.45/295.17 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.17 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.17 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.17 quicksort(nil) -> nil 1132.45/295.17 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.17 1132.45/295.17 S is empty. 1132.45/295.17 Rewrite Strategy: INNERMOST 1132.45/295.17 ---------------------------------------- 1132.45/295.17 1132.45/295.17 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1132.45/295.17 Renamed function symbols to avoid clashes with predefined symbol. 1132.45/295.17 ---------------------------------------- 1132.45/295.17 1132.45/295.17 (2) 1132.45/295.17 Obligation: 1132.45/295.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1132.45/295.17 1132.45/295.17 1132.45/295.17 The TRS R consists of the following rules: 1132.45/295.17 1132.45/295.17 minus(x, 0') -> x 1132.45/295.17 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.17 quot(0', s(y)) -> 0' 1132.45/295.17 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.17 le(0', y) -> true 1132.45/295.17 le(s(x), 0') -> false 1132.45/295.17 le(s(x), s(y)) -> le(x, y) 1132.45/295.17 app(nil, y) -> y 1132.45/295.17 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.17 low(n, nil) -> nil 1132.45/295.17 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.17 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.17 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.17 high(n, nil) -> nil 1132.45/295.17 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.17 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.17 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.17 quicksort(nil) -> nil 1132.45/295.17 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.17 1132.45/295.17 S is empty. 1132.45/295.17 Rewrite Strategy: INNERMOST 1132.45/295.17 ---------------------------------------- 1132.45/295.17 1132.45/295.17 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1132.45/295.17 Infered types. 1132.45/295.17 ---------------------------------------- 1132.45/295.17 1132.45/295.17 (4) 1132.45/295.17 Obligation: 1132.45/295.17 Innermost TRS: 1132.45/295.17 Rules: 1132.45/295.17 minus(x, 0') -> x 1132.45/295.17 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.17 quot(0', s(y)) -> 0' 1132.45/295.17 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.17 le(0', y) -> true 1132.45/295.17 le(s(x), 0') -> false 1132.45/295.17 le(s(x), s(y)) -> le(x, y) 1132.45/295.17 app(nil, y) -> y 1132.45/295.17 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.17 low(n, nil) -> nil 1132.45/295.17 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.17 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.17 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.17 high(n, nil) -> nil 1132.45/295.17 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.17 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.17 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.17 quicksort(nil) -> nil 1132.45/295.17 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.17 1132.45/295.17 Types: 1132.45/295.17 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (5) OrderProof (LOWER BOUND(ID)) 1132.45/295.18 Heuristically decided to analyse the following defined symbols: 1132.45/295.18 minus, quot, le, app, low, high, quicksort 1132.45/295.18 1132.45/295.18 They will be analysed ascendingly in the following order: 1132.45/295.18 minus < quot 1132.45/295.18 le < low 1132.45/295.18 le < high 1132.45/295.18 app < quicksort 1132.45/295.18 low < quicksort 1132.45/295.18 high < quicksort 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (6) 1132.45/295.18 Obligation: 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 minus, quot, le, app, low, high, quicksort 1132.45/295.18 1132.45/295.18 They will be analysed ascendingly in the following order: 1132.45/295.18 minus < quot 1132.45/295.18 le < low 1132.45/295.18 le < high 1132.45/295.18 app < quicksort 1132.45/295.18 low < quicksort 1132.45/295.18 high < quicksort 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1132.45/295.18 Proved the following rewrite lemma: 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1132.45/295.18 1132.45/295.18 Induction Base: 1132.45/295.18 minus(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1132.45/295.18 gen_0':s4_0(0) 1132.45/295.18 1132.45/295.18 Induction Step: 1132.45/295.18 minus(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1) 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH 1132.45/295.18 gen_0':s4_0(0) 1132.45/295.18 1132.45/295.18 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (8) 1132.45/295.18 Complex Obligation (BEST) 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (9) 1132.45/295.18 Obligation: 1132.45/295.18 Proved the lower bound n^1 for the following obligation: 1132.45/295.18 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 minus, quot, le, app, low, high, quicksort 1132.45/295.18 1132.45/295.18 They will be analysed ascendingly in the following order: 1132.45/295.18 minus < quot 1132.45/295.18 le < low 1132.45/295.18 le < high 1132.45/295.18 app < quicksort 1132.45/295.18 low < quicksort 1132.45/295.18 high < quicksort 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (10) LowerBoundPropagationProof (FINISHED) 1132.45/295.18 Propagated lower bound. 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (11) 1132.45/295.18 BOUNDS(n^1, INF) 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (12) 1132.45/295.18 Obligation: 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Lemmas: 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 quot, le, app, low, high, quicksort 1132.45/295.18 1132.45/295.18 They will be analysed ascendingly in the following order: 1132.45/295.18 le < low 1132.45/295.18 le < high 1132.45/295.18 app < quicksort 1132.45/295.18 low < quicksort 1132.45/295.18 high < quicksort 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1132.45/295.18 Proved the following rewrite lemma: 1132.45/295.18 le(gen_0':s4_0(n539_0), gen_0':s4_0(n539_0)) -> true, rt in Omega(1 + n539_0) 1132.45/295.18 1132.45/295.18 Induction Base: 1132.45/295.18 le(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1132.45/295.18 true 1132.45/295.18 1132.45/295.18 Induction Step: 1132.45/295.18 le(gen_0':s4_0(+(n539_0, 1)), gen_0':s4_0(+(n539_0, 1))) ->_R^Omega(1) 1132.45/295.18 le(gen_0':s4_0(n539_0), gen_0':s4_0(n539_0)) ->_IH 1132.45/295.18 true 1132.45/295.18 1132.45/295.18 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (14) 1132.45/295.18 Obligation: 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Lemmas: 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1132.45/295.18 le(gen_0':s4_0(n539_0), gen_0':s4_0(n539_0)) -> true, rt in Omega(1 + n539_0) 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 app, low, high, quicksort 1132.45/295.18 1132.45/295.18 They will be analysed ascendingly in the following order: 1132.45/295.18 app < quicksort 1132.45/295.18 low < quicksort 1132.45/295.18 high < quicksort 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1132.45/295.18 Proved the following rewrite lemma: 1132.45/295.18 app(gen_nil:add5_0(n874_0), gen_nil:add5_0(b)) -> gen_nil:add5_0(+(n874_0, b)), rt in Omega(1 + n874_0) 1132.45/295.18 1132.45/295.18 Induction Base: 1132.45/295.18 app(gen_nil:add5_0(0), gen_nil:add5_0(b)) ->_R^Omega(1) 1132.45/295.18 gen_nil:add5_0(b) 1132.45/295.18 1132.45/295.18 Induction Step: 1132.45/295.18 app(gen_nil:add5_0(+(n874_0, 1)), gen_nil:add5_0(b)) ->_R^Omega(1) 1132.45/295.18 add(0', app(gen_nil:add5_0(n874_0), gen_nil:add5_0(b))) ->_IH 1132.45/295.18 add(0', gen_nil:add5_0(+(b, c875_0))) 1132.45/295.18 1132.45/295.18 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (16) 1132.45/295.18 Obligation: 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Lemmas: 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1132.45/295.18 le(gen_0':s4_0(n539_0), gen_0':s4_0(n539_0)) -> true, rt in Omega(1 + n539_0) 1132.45/295.18 app(gen_nil:add5_0(n874_0), gen_nil:add5_0(b)) -> gen_nil:add5_0(+(n874_0, b)), rt in Omega(1 + n874_0) 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 low, high, quicksort 1132.45/295.18 1132.45/295.18 They will be analysed ascendingly in the following order: 1132.45/295.18 low < quicksort 1132.45/295.18 high < quicksort 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1132.45/295.18 Proved the following rewrite lemma: 1132.45/295.18 low(gen_0':s4_0(0), gen_nil:add5_0(n1895_0)) -> gen_nil:add5_0(n1895_0), rt in Omega(1 + n1895_0) 1132.45/295.18 1132.45/295.18 Induction Base: 1132.45/295.18 low(gen_0':s4_0(0), gen_nil:add5_0(0)) ->_R^Omega(1) 1132.45/295.18 nil 1132.45/295.18 1132.45/295.18 Induction Step: 1132.45/295.18 low(gen_0':s4_0(0), gen_nil:add5_0(+(n1895_0, 1))) ->_R^Omega(1) 1132.45/295.18 if_low(le(0', gen_0':s4_0(0)), gen_0':s4_0(0), add(0', gen_nil:add5_0(n1895_0))) ->_L^Omega(1) 1132.45/295.18 if_low(true, gen_0':s4_0(0), add(0', gen_nil:add5_0(n1895_0))) ->_R^Omega(1) 1132.45/295.18 add(0', low(gen_0':s4_0(0), gen_nil:add5_0(n1895_0))) ->_IH 1132.45/295.18 add(0', gen_nil:add5_0(c1896_0)) 1132.45/295.18 1132.45/295.18 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (18) 1132.45/295.18 Obligation: 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Lemmas: 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1132.45/295.18 le(gen_0':s4_0(n539_0), gen_0':s4_0(n539_0)) -> true, rt in Omega(1 + n539_0) 1132.45/295.18 app(gen_nil:add5_0(n874_0), gen_nil:add5_0(b)) -> gen_nil:add5_0(+(n874_0, b)), rt in Omega(1 + n874_0) 1132.45/295.18 low(gen_0':s4_0(0), gen_nil:add5_0(n1895_0)) -> gen_nil:add5_0(n1895_0), rt in Omega(1 + n1895_0) 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 high, quicksort 1132.45/295.18 1132.45/295.18 They will be analysed ascendingly in the following order: 1132.45/295.18 high < quicksort 1132.45/295.18 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1132.45/295.18 Proved the following rewrite lemma: 1132.45/295.18 high(gen_0':s4_0(0), gen_nil:add5_0(n2627_0)) -> gen_nil:add5_0(0), rt in Omega(1 + n2627_0) 1132.45/295.18 1132.45/295.18 Induction Base: 1132.45/295.18 high(gen_0':s4_0(0), gen_nil:add5_0(0)) ->_R^Omega(1) 1132.45/295.18 nil 1132.45/295.18 1132.45/295.18 Induction Step: 1132.45/295.18 high(gen_0':s4_0(0), gen_nil:add5_0(+(n2627_0, 1))) ->_R^Omega(1) 1132.45/295.18 if_high(le(0', gen_0':s4_0(0)), gen_0':s4_0(0), add(0', gen_nil:add5_0(n2627_0))) ->_L^Omega(1) 1132.45/295.18 if_high(true, gen_0':s4_0(0), add(0', gen_nil:add5_0(n2627_0))) ->_R^Omega(1) 1132.45/295.18 high(gen_0':s4_0(0), gen_nil:add5_0(n2627_0)) ->_IH 1132.45/295.18 gen_nil:add5_0(0) 1132.45/295.18 1132.45/295.18 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (20) 1132.45/295.18 Obligation: 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Lemmas: 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1132.45/295.18 le(gen_0':s4_0(n539_0), gen_0':s4_0(n539_0)) -> true, rt in Omega(1 + n539_0) 1132.45/295.18 app(gen_nil:add5_0(n874_0), gen_nil:add5_0(b)) -> gen_nil:add5_0(+(n874_0, b)), rt in Omega(1 + n874_0) 1132.45/295.18 low(gen_0':s4_0(0), gen_nil:add5_0(n1895_0)) -> gen_nil:add5_0(n1895_0), rt in Omega(1 + n1895_0) 1132.45/295.18 high(gen_0':s4_0(0), gen_nil:add5_0(n2627_0)) -> gen_nil:add5_0(0), rt in Omega(1 + n2627_0) 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 quicksort 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (21) RewriteLemmaProof (LOWER BOUND(ID)) 1132.45/295.18 Proved the following rewrite lemma: 1132.45/295.18 quicksort(gen_nil:add5_0(n3355_0)) -> gen_nil:add5_0(n3355_0), rt in Omega(1 + n3355_0 + n3355_0^2) 1132.45/295.18 1132.45/295.18 Induction Base: 1132.45/295.18 quicksort(gen_nil:add5_0(0)) ->_R^Omega(1) 1132.45/295.18 nil 1132.45/295.18 1132.45/295.18 Induction Step: 1132.45/295.18 quicksort(gen_nil:add5_0(+(n3355_0, 1))) ->_R^Omega(1) 1132.45/295.18 app(quicksort(low(0', gen_nil:add5_0(n3355_0))), add(0', quicksort(high(0', gen_nil:add5_0(n3355_0))))) ->_L^Omega(1 + n3355_0) 1132.45/295.18 app(quicksort(gen_nil:add5_0(n3355_0)), add(0', quicksort(high(0', gen_nil:add5_0(n3355_0))))) ->_IH 1132.45/295.18 app(gen_nil:add5_0(c3356_0), add(0', quicksort(high(0', gen_nil:add5_0(n3355_0))))) ->_L^Omega(1 + n3355_0) 1132.45/295.18 app(gen_nil:add5_0(n3355_0), add(0', quicksort(gen_nil:add5_0(0)))) ->_R^Omega(1) 1132.45/295.18 app(gen_nil:add5_0(n3355_0), add(0', nil)) ->_L^Omega(1 + n3355_0) 1132.45/295.18 gen_nil:add5_0(+(n3355_0, +(0, 1))) 1132.45/295.18 1132.45/295.18 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (22) 1132.45/295.18 Obligation: 1132.45/295.18 Proved the lower bound n^2 for the following obligation: 1132.45/295.18 1132.45/295.18 Innermost TRS: 1132.45/295.18 Rules: 1132.45/295.18 minus(x, 0') -> x 1132.45/295.18 minus(s(x), s(y)) -> minus(x, y) 1132.45/295.18 quot(0', s(y)) -> 0' 1132.45/295.18 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 1132.45/295.18 le(0', y) -> true 1132.45/295.18 le(s(x), 0') -> false 1132.45/295.18 le(s(x), s(y)) -> le(x, y) 1132.45/295.18 app(nil, y) -> y 1132.45/295.18 app(add(n, x), y) -> add(n, app(x, y)) 1132.45/295.18 low(n, nil) -> nil 1132.45/295.18 low(n, add(m, x)) -> if_low(le(m, n), n, add(m, x)) 1132.45/295.18 if_low(true, n, add(m, x)) -> add(m, low(n, x)) 1132.45/295.18 if_low(false, n, add(m, x)) -> low(n, x) 1132.45/295.18 high(n, nil) -> nil 1132.45/295.18 high(n, add(m, x)) -> if_high(le(m, n), n, add(m, x)) 1132.45/295.18 if_high(true, n, add(m, x)) -> high(n, x) 1132.45/295.18 if_high(false, n, add(m, x)) -> add(m, high(n, x)) 1132.45/295.18 quicksort(nil) -> nil 1132.45/295.18 quicksort(add(n, x)) -> app(quicksort(low(n, x)), add(n, quicksort(high(n, x)))) 1132.45/295.18 1132.45/295.18 Types: 1132.45/295.18 minus :: 0':s -> 0':s -> 0':s 1132.45/295.18 0' :: 0':s 1132.45/295.18 s :: 0':s -> 0':s 1132.45/295.18 quot :: 0':s -> 0':s -> 0':s 1132.45/295.18 le :: 0':s -> 0':s -> true:false 1132.45/295.18 true :: true:false 1132.45/295.18 false :: true:false 1132.45/295.18 app :: nil:add -> nil:add -> nil:add 1132.45/295.18 nil :: nil:add 1132.45/295.18 add :: 0':s -> nil:add -> nil:add 1132.45/295.18 low :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_low :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 high :: 0':s -> nil:add -> nil:add 1132.45/295.18 if_high :: true:false -> 0':s -> nil:add -> nil:add 1132.45/295.18 quicksort :: nil:add -> nil:add 1132.45/295.18 hole_0':s1_0 :: 0':s 1132.45/295.18 hole_true:false2_0 :: true:false 1132.45/295.18 hole_nil:add3_0 :: nil:add 1132.45/295.18 gen_0':s4_0 :: Nat -> 0':s 1132.45/295.18 gen_nil:add5_0 :: Nat -> nil:add 1132.45/295.18 1132.45/295.18 1132.45/295.18 Lemmas: 1132.45/295.18 minus(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1132.45/295.18 le(gen_0':s4_0(n539_0), gen_0':s4_0(n539_0)) -> true, rt in Omega(1 + n539_0) 1132.45/295.18 app(gen_nil:add5_0(n874_0), gen_nil:add5_0(b)) -> gen_nil:add5_0(+(n874_0, b)), rt in Omega(1 + n874_0) 1132.45/295.18 low(gen_0':s4_0(0), gen_nil:add5_0(n1895_0)) -> gen_nil:add5_0(n1895_0), rt in Omega(1 + n1895_0) 1132.45/295.18 high(gen_0':s4_0(0), gen_nil:add5_0(n2627_0)) -> gen_nil:add5_0(0), rt in Omega(1 + n2627_0) 1132.45/295.18 1132.45/295.18 1132.45/295.18 Generator Equations: 1132.45/295.18 gen_0':s4_0(0) <=> 0' 1132.45/295.18 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1132.45/295.18 gen_nil:add5_0(0) <=> nil 1132.45/295.18 gen_nil:add5_0(+(x, 1)) <=> add(0', gen_nil:add5_0(x)) 1132.45/295.18 1132.45/295.18 1132.45/295.18 The following defined symbols remain to be analysed: 1132.45/295.18 quicksort 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (23) LowerBoundPropagationProof (FINISHED) 1132.45/295.18 Propagated lower bound. 1132.45/295.18 ---------------------------------------- 1132.45/295.18 1132.45/295.18 (24) 1132.45/295.18 BOUNDS(n^2, INF) 1132.64/295.25 EOF