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