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