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