304.44/291.48 WORST_CASE(Omega(n^2), ?) 304.44/291.49 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 304.44/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 304.44/291.49 304.44/291.49 304.44/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 304.44/291.49 304.44/291.49 (0) CpxTRS 304.44/291.49 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 304.44/291.49 (2) CpxTRS 304.44/291.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 304.44/291.49 (4) typed CpxTrs 304.44/291.49 (5) OrderProof [LOWER BOUND(ID), 0 ms] 304.44/291.49 (6) typed CpxTrs 304.44/291.49 (7) RewriteLemmaProof [LOWER BOUND(ID), 265 ms] 304.44/291.49 (8) BEST 304.44/291.49 (9) proven lower bound 304.44/291.49 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 304.44/291.49 (11) BOUNDS(n^1, INF) 304.44/291.49 (12) typed CpxTrs 304.44/291.49 (13) RewriteLemmaProof [LOWER BOUND(ID), 151 ms] 304.44/291.49 (14) proven lower bound 304.44/291.49 (15) LowerBoundPropagationProof [FINISHED, 0 ms] 304.44/291.49 (16) BOUNDS(n^2, INF) 304.44/291.49 304.44/291.49 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (0) 304.44/291.49 Obligation: 304.44/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 304.44/291.49 304.44/291.49 304.44/291.49 The TRS R consists of the following rules: 304.44/291.49 304.44/291.49 isEmpty(empty) -> true 304.44/291.49 isEmpty(node(l, r)) -> false 304.44/291.49 left(empty) -> empty 304.44/291.49 left(node(l, r)) -> l 304.44/291.49 right(empty) -> empty 304.44/291.49 right(node(l, r)) -> r 304.44/291.49 inc(0) -> s(0) 304.44/291.49 inc(s(x)) -> s(inc(x)) 304.44/291.49 count(n, x) -> if(isEmpty(n), isEmpty(left(n)), right(n), node(left(left(n)), node(right(left(n)), right(n))), x, inc(x)) 304.44/291.49 if(true, b, n, m, x, y) -> x 304.44/291.49 if(false, false, n, m, x, y) -> count(m, x) 304.44/291.49 if(false, true, n, m, x, y) -> count(n, y) 304.44/291.49 nrOfNodes(n) -> count(n, 0) 304.44/291.49 304.44/291.49 S is empty. 304.44/291.49 Rewrite Strategy: FULL 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 304.44/291.49 Renamed function symbols to avoid clashes with predefined symbol. 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (2) 304.44/291.49 Obligation: 304.44/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 304.44/291.49 304.44/291.49 304.44/291.49 The TRS R consists of the following rules: 304.44/291.49 304.44/291.49 isEmpty(empty) -> true 304.44/291.49 isEmpty(node(l, r)) -> false 304.44/291.49 left(empty) -> empty 304.44/291.49 left(node(l, r)) -> l 304.44/291.49 right(empty) -> empty 304.44/291.49 right(node(l, r)) -> r 304.44/291.49 inc(0') -> s(0') 304.44/291.49 inc(s(x)) -> s(inc(x)) 304.44/291.49 count(n, x) -> if(isEmpty(n), isEmpty(left(n)), right(n), node(left(left(n)), node(right(left(n)), right(n))), x, inc(x)) 304.44/291.49 if(true, b, n, m, x, y) -> x 304.44/291.49 if(false, false, n, m, x, y) -> count(m, x) 304.44/291.49 if(false, true, n, m, x, y) -> count(n, y) 304.44/291.49 nrOfNodes(n) -> count(n, 0') 304.44/291.49 304.44/291.49 S is empty. 304.44/291.49 Rewrite Strategy: FULL 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 304.44/291.49 Infered types. 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (4) 304.44/291.49 Obligation: 304.44/291.49 TRS: 304.44/291.49 Rules: 304.44/291.49 isEmpty(empty) -> true 304.44/291.49 isEmpty(node(l, r)) -> false 304.44/291.49 left(empty) -> empty 304.44/291.49 left(node(l, r)) -> l 304.44/291.49 right(empty) -> empty 304.44/291.49 right(node(l, r)) -> r 304.44/291.49 inc(0') -> s(0') 304.44/291.49 inc(s(x)) -> s(inc(x)) 304.44/291.49 count(n, x) -> if(isEmpty(n), isEmpty(left(n)), right(n), node(left(left(n)), node(right(left(n)), right(n))), x, inc(x)) 304.44/291.49 if(true, b, n, m, x, y) -> x 304.44/291.49 if(false, false, n, m, x, y) -> count(m, x) 304.44/291.49 if(false, true, n, m, x, y) -> count(n, y) 304.44/291.49 nrOfNodes(n) -> count(n, 0') 304.44/291.49 304.44/291.49 Types: 304.44/291.49 isEmpty :: empty:node -> true:false 304.44/291.49 empty :: empty:node 304.44/291.49 true :: true:false 304.44/291.49 node :: empty:node -> empty:node -> empty:node 304.44/291.49 false :: true:false 304.44/291.49 left :: empty:node -> empty:node 304.44/291.49 right :: empty:node -> empty:node 304.44/291.49 inc :: 0':s -> 0':s 304.44/291.49 0' :: 0':s 304.44/291.49 s :: 0':s -> 0':s 304.44/291.49 count :: empty:node -> 0':s -> 0':s 304.44/291.49 if :: true:false -> true:false -> empty:node -> empty:node -> 0':s -> 0':s -> 0':s 304.44/291.49 nrOfNodes :: empty:node -> 0':s 304.44/291.49 hole_true:false1_0 :: true:false 304.44/291.49 hole_empty:node2_0 :: empty:node 304.44/291.49 hole_0':s3_0 :: 0':s 304.44/291.49 gen_empty:node4_0 :: Nat -> empty:node 304.44/291.49 gen_0':s5_0 :: Nat -> 0':s 304.44/291.49 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (5) OrderProof (LOWER BOUND(ID)) 304.44/291.49 Heuristically decided to analyse the following defined symbols: 304.44/291.49 inc, count 304.44/291.49 304.44/291.49 They will be analysed ascendingly in the following order: 304.44/291.49 inc < count 304.44/291.49 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (6) 304.44/291.49 Obligation: 304.44/291.49 TRS: 304.44/291.49 Rules: 304.44/291.49 isEmpty(empty) -> true 304.44/291.49 isEmpty(node(l, r)) -> false 304.44/291.49 left(empty) -> empty 304.44/291.49 left(node(l, r)) -> l 304.44/291.49 right(empty) -> empty 304.44/291.49 right(node(l, r)) -> r 304.44/291.49 inc(0') -> s(0') 304.44/291.49 inc(s(x)) -> s(inc(x)) 304.44/291.49 count(n, x) -> if(isEmpty(n), isEmpty(left(n)), right(n), node(left(left(n)), node(right(left(n)), right(n))), x, inc(x)) 304.44/291.49 if(true, b, n, m, x, y) -> x 304.44/291.49 if(false, false, n, m, x, y) -> count(m, x) 304.44/291.49 if(false, true, n, m, x, y) -> count(n, y) 304.44/291.49 nrOfNodes(n) -> count(n, 0') 304.44/291.49 304.44/291.49 Types: 304.44/291.49 isEmpty :: empty:node -> true:false 304.44/291.49 empty :: empty:node 304.44/291.49 true :: true:false 304.44/291.49 node :: empty:node -> empty:node -> empty:node 304.44/291.49 false :: true:false 304.44/291.49 left :: empty:node -> empty:node 304.44/291.49 right :: empty:node -> empty:node 304.44/291.49 inc :: 0':s -> 0':s 304.44/291.49 0' :: 0':s 304.44/291.49 s :: 0':s -> 0':s 304.44/291.49 count :: empty:node -> 0':s -> 0':s 304.44/291.49 if :: true:false -> true:false -> empty:node -> empty:node -> 0':s -> 0':s -> 0':s 304.44/291.49 nrOfNodes :: empty:node -> 0':s 304.44/291.49 hole_true:false1_0 :: true:false 304.44/291.49 hole_empty:node2_0 :: empty:node 304.44/291.49 hole_0':s3_0 :: 0':s 304.44/291.49 gen_empty:node4_0 :: Nat -> empty:node 304.44/291.49 gen_0':s5_0 :: Nat -> 0':s 304.44/291.49 304.44/291.49 304.44/291.49 Generator Equations: 304.44/291.49 gen_empty:node4_0(0) <=> empty 304.44/291.49 gen_empty:node4_0(+(x, 1)) <=> node(empty, gen_empty:node4_0(x)) 304.44/291.49 gen_0':s5_0(0) <=> 0' 304.44/291.49 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 304.44/291.49 304.44/291.49 304.44/291.49 The following defined symbols remain to be analysed: 304.44/291.49 inc, count 304.44/291.49 304.44/291.49 They will be analysed ascendingly in the following order: 304.44/291.49 inc < count 304.44/291.49 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (7) RewriteLemmaProof (LOWER BOUND(ID)) 304.44/291.49 Proved the following rewrite lemma: 304.44/291.49 inc(gen_0':s5_0(n7_0)) -> gen_0':s5_0(+(1, n7_0)), rt in Omega(1 + n7_0) 304.44/291.49 304.44/291.49 Induction Base: 304.44/291.49 inc(gen_0':s5_0(0)) ->_R^Omega(1) 304.44/291.49 s(0') 304.44/291.49 304.44/291.49 Induction Step: 304.44/291.49 inc(gen_0':s5_0(+(n7_0, 1))) ->_R^Omega(1) 304.44/291.49 s(inc(gen_0':s5_0(n7_0))) ->_IH 304.44/291.49 s(gen_0':s5_0(+(1, c8_0))) 304.44/291.49 304.44/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (8) 304.44/291.49 Complex Obligation (BEST) 304.44/291.49 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (9) 304.44/291.49 Obligation: 304.44/291.49 Proved the lower bound n^1 for the following obligation: 304.44/291.49 304.44/291.49 TRS: 304.44/291.49 Rules: 304.44/291.49 isEmpty(empty) -> true 304.44/291.49 isEmpty(node(l, r)) -> false 304.44/291.49 left(empty) -> empty 304.44/291.49 left(node(l, r)) -> l 304.44/291.49 right(empty) -> empty 304.44/291.49 right(node(l, r)) -> r 304.44/291.49 inc(0') -> s(0') 304.44/291.49 inc(s(x)) -> s(inc(x)) 304.44/291.49 count(n, x) -> if(isEmpty(n), isEmpty(left(n)), right(n), node(left(left(n)), node(right(left(n)), right(n))), x, inc(x)) 304.44/291.49 if(true, b, n, m, x, y) -> x 304.44/291.49 if(false, false, n, m, x, y) -> count(m, x) 304.44/291.49 if(false, true, n, m, x, y) -> count(n, y) 304.44/291.49 nrOfNodes(n) -> count(n, 0') 304.44/291.49 304.44/291.49 Types: 304.44/291.49 isEmpty :: empty:node -> true:false 304.44/291.49 empty :: empty:node 304.44/291.49 true :: true:false 304.44/291.49 node :: empty:node -> empty:node -> empty:node 304.44/291.49 false :: true:false 304.44/291.49 left :: empty:node -> empty:node 304.44/291.49 right :: empty:node -> empty:node 304.44/291.49 inc :: 0':s -> 0':s 304.44/291.49 0' :: 0':s 304.44/291.49 s :: 0':s -> 0':s 304.44/291.49 count :: empty:node -> 0':s -> 0':s 304.44/291.49 if :: true:false -> true:false -> empty:node -> empty:node -> 0':s -> 0':s -> 0':s 304.44/291.49 nrOfNodes :: empty:node -> 0':s 304.44/291.49 hole_true:false1_0 :: true:false 304.44/291.49 hole_empty:node2_0 :: empty:node 304.44/291.49 hole_0':s3_0 :: 0':s 304.44/291.49 gen_empty:node4_0 :: Nat -> empty:node 304.44/291.49 gen_0':s5_0 :: Nat -> 0':s 304.44/291.49 304.44/291.49 304.44/291.49 Generator Equations: 304.44/291.49 gen_empty:node4_0(0) <=> empty 304.44/291.49 gen_empty:node4_0(+(x, 1)) <=> node(empty, gen_empty:node4_0(x)) 304.44/291.49 gen_0':s5_0(0) <=> 0' 304.44/291.49 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 304.44/291.49 304.44/291.49 304.44/291.49 The following defined symbols remain to be analysed: 304.44/291.49 inc, count 304.44/291.49 304.44/291.49 They will be analysed ascendingly in the following order: 304.44/291.49 inc < count 304.44/291.49 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (10) LowerBoundPropagationProof (FINISHED) 304.44/291.49 Propagated lower bound. 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (11) 304.44/291.49 BOUNDS(n^1, INF) 304.44/291.49 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (12) 304.44/291.49 Obligation: 304.44/291.49 TRS: 304.44/291.49 Rules: 304.44/291.49 isEmpty(empty) -> true 304.44/291.49 isEmpty(node(l, r)) -> false 304.44/291.49 left(empty) -> empty 304.44/291.49 left(node(l, r)) -> l 304.44/291.49 right(empty) -> empty 304.44/291.49 right(node(l, r)) -> r 304.44/291.49 inc(0') -> s(0') 304.44/291.49 inc(s(x)) -> s(inc(x)) 304.44/291.49 count(n, x) -> if(isEmpty(n), isEmpty(left(n)), right(n), node(left(left(n)), node(right(left(n)), right(n))), x, inc(x)) 304.44/291.49 if(true, b, n, m, x, y) -> x 304.44/291.49 if(false, false, n, m, x, y) -> count(m, x) 304.44/291.49 if(false, true, n, m, x, y) -> count(n, y) 304.44/291.49 nrOfNodes(n) -> count(n, 0') 304.44/291.49 304.44/291.49 Types: 304.44/291.49 isEmpty :: empty:node -> true:false 304.44/291.49 empty :: empty:node 304.44/291.49 true :: true:false 304.44/291.49 node :: empty:node -> empty:node -> empty:node 304.44/291.49 false :: true:false 304.44/291.49 left :: empty:node -> empty:node 304.44/291.49 right :: empty:node -> empty:node 304.44/291.49 inc :: 0':s -> 0':s 304.44/291.49 0' :: 0':s 304.44/291.49 s :: 0':s -> 0':s 304.44/291.49 count :: empty:node -> 0':s -> 0':s 304.44/291.49 if :: true:false -> true:false -> empty:node -> empty:node -> 0':s -> 0':s -> 0':s 304.44/291.49 nrOfNodes :: empty:node -> 0':s 304.44/291.49 hole_true:false1_0 :: true:false 304.44/291.49 hole_empty:node2_0 :: empty:node 304.44/291.49 hole_0':s3_0 :: 0':s 304.44/291.49 gen_empty:node4_0 :: Nat -> empty:node 304.44/291.49 gen_0':s5_0 :: Nat -> 0':s 304.44/291.49 304.44/291.49 304.44/291.49 Lemmas: 304.44/291.49 inc(gen_0':s5_0(n7_0)) -> gen_0':s5_0(+(1, n7_0)), rt in Omega(1 + n7_0) 304.44/291.49 304.44/291.49 304.44/291.49 Generator Equations: 304.44/291.49 gen_empty:node4_0(0) <=> empty 304.44/291.49 gen_empty:node4_0(+(x, 1)) <=> node(empty, gen_empty:node4_0(x)) 304.44/291.49 gen_0':s5_0(0) <=> 0' 304.44/291.49 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 304.44/291.49 304.44/291.49 304.44/291.49 The following defined symbols remain to be analysed: 304.44/291.49 count 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (13) RewriteLemmaProof (LOWER BOUND(ID)) 304.44/291.49 Proved the following rewrite lemma: 304.44/291.49 count(gen_empty:node4_0(n263_0), gen_0':s5_0(b)) -> gen_0':s5_0(+(n263_0, b)), rt in Omega(1 + b + b*n263_0 + n263_0) 304.44/291.49 304.44/291.49 Induction Base: 304.44/291.49 count(gen_empty:node4_0(0), gen_0':s5_0(b)) ->_R^Omega(1) 304.44/291.49 if(isEmpty(gen_empty:node4_0(0)), isEmpty(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)), node(left(left(gen_empty:node4_0(0))), node(right(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, isEmpty(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)), node(left(left(gen_empty:node4_0(0))), node(right(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, isEmpty(empty), right(gen_empty:node4_0(0)), node(left(left(gen_empty:node4_0(0))), node(right(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, true, right(gen_empty:node4_0(0)), node(left(left(gen_empty:node4_0(0))), node(right(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, true, empty, node(left(left(gen_empty:node4_0(0))), node(right(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, true, empty, node(left(empty), node(right(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, true, empty, node(empty, node(right(left(gen_empty:node4_0(0))), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, true, empty, node(empty, node(right(empty), right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, true, empty, node(empty, node(empty, right(gen_empty:node4_0(0)))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(true, true, empty, node(empty, node(empty, empty)), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_L^Omega(1 + b) 304.44/291.49 if(true, true, empty, node(empty, node(empty, empty)), gen_0':s5_0(b), gen_0':s5_0(+(1, b))) ->_R^Omega(1) 304.44/291.49 gen_0':s5_0(b) 304.44/291.49 304.44/291.49 Induction Step: 304.44/291.49 count(gen_empty:node4_0(+(n263_0, 1)), gen_0':s5_0(b)) ->_R^Omega(1) 304.44/291.49 if(isEmpty(gen_empty:node4_0(+(n263_0, 1))), isEmpty(left(gen_empty:node4_0(+(n263_0, 1)))), right(gen_empty:node4_0(+(n263_0, 1))), node(left(left(gen_empty:node4_0(+(n263_0, 1)))), node(right(left(gen_empty:node4_0(+(n263_0, 1)))), right(gen_empty:node4_0(+(n263_0, 1))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, isEmpty(left(gen_empty:node4_0(+(1, n263_0)))), right(gen_empty:node4_0(+(1, n263_0))), node(left(left(gen_empty:node4_0(+(1, n263_0)))), node(right(left(gen_empty:node4_0(+(1, n263_0)))), right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, isEmpty(empty), right(gen_empty:node4_0(+(1, n263_0))), node(left(left(gen_empty:node4_0(+(1, n263_0)))), node(right(left(gen_empty:node4_0(+(1, n263_0)))), right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, true, right(gen_empty:node4_0(+(1, n263_0))), node(left(left(gen_empty:node4_0(+(1, n263_0)))), node(right(left(gen_empty:node4_0(+(1, n263_0)))), right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, true, gen_empty:node4_0(n263_0), node(left(left(gen_empty:node4_0(+(1, n263_0)))), node(right(left(gen_empty:node4_0(+(1, n263_0)))), right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, true, gen_empty:node4_0(n263_0), node(left(empty), node(right(left(gen_empty:node4_0(+(1, n263_0)))), right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, true, gen_empty:node4_0(n263_0), node(empty, node(right(left(gen_empty:node4_0(+(1, n263_0)))), right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, true, gen_empty:node4_0(n263_0), node(empty, node(right(empty), right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, true, gen_empty:node4_0(n263_0), node(empty, node(empty, right(gen_empty:node4_0(+(1, n263_0))))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_R^Omega(1) 304.44/291.49 if(false, true, gen_empty:node4_0(n263_0), node(empty, node(empty, gen_empty:node4_0(n263_0))), gen_0':s5_0(b), inc(gen_0':s5_0(b))) ->_L^Omega(1 + b) 304.44/291.49 if(false, true, gen_empty:node4_0(n263_0), node(empty, node(empty, gen_empty:node4_0(n263_0))), gen_0':s5_0(b), gen_0':s5_0(+(1, b))) ->_R^Omega(1) 304.44/291.49 count(gen_empty:node4_0(n263_0), gen_0':s5_0(+(1, b))) ->_IH 304.44/291.49 gen_0':s5_0(+(+(1, b), c264_0)) 304.44/291.49 304.44/291.49 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (14) 304.44/291.49 Obligation: 304.44/291.49 Proved the lower bound n^2 for the following obligation: 304.44/291.49 304.44/291.49 TRS: 304.44/291.49 Rules: 304.44/291.49 isEmpty(empty) -> true 304.44/291.49 isEmpty(node(l, r)) -> false 304.44/291.49 left(empty) -> empty 304.44/291.49 left(node(l, r)) -> l 304.44/291.49 right(empty) -> empty 304.44/291.49 right(node(l, r)) -> r 304.44/291.49 inc(0') -> s(0') 304.44/291.49 inc(s(x)) -> s(inc(x)) 304.44/291.49 count(n, x) -> if(isEmpty(n), isEmpty(left(n)), right(n), node(left(left(n)), node(right(left(n)), right(n))), x, inc(x)) 304.44/291.49 if(true, b, n, m, x, y) -> x 304.44/291.49 if(false, false, n, m, x, y) -> count(m, x) 304.44/291.49 if(false, true, n, m, x, y) -> count(n, y) 304.44/291.49 nrOfNodes(n) -> count(n, 0') 304.44/291.49 304.44/291.49 Types: 304.44/291.49 isEmpty :: empty:node -> true:false 304.44/291.49 empty :: empty:node 304.44/291.49 true :: true:false 304.44/291.49 node :: empty:node -> empty:node -> empty:node 304.44/291.49 false :: true:false 304.44/291.49 left :: empty:node -> empty:node 304.44/291.49 right :: empty:node -> empty:node 304.44/291.49 inc :: 0':s -> 0':s 304.44/291.49 0' :: 0':s 304.44/291.49 s :: 0':s -> 0':s 304.44/291.49 count :: empty:node -> 0':s -> 0':s 304.44/291.49 if :: true:false -> true:false -> empty:node -> empty:node -> 0':s -> 0':s -> 0':s 304.44/291.49 nrOfNodes :: empty:node -> 0':s 304.44/291.49 hole_true:false1_0 :: true:false 304.44/291.49 hole_empty:node2_0 :: empty:node 304.44/291.49 hole_0':s3_0 :: 0':s 304.44/291.49 gen_empty:node4_0 :: Nat -> empty:node 304.44/291.49 gen_0':s5_0 :: Nat -> 0':s 304.44/291.49 304.44/291.49 304.44/291.49 Lemmas: 304.44/291.49 inc(gen_0':s5_0(n7_0)) -> gen_0':s5_0(+(1, n7_0)), rt in Omega(1 + n7_0) 304.44/291.49 304.44/291.49 304.44/291.49 Generator Equations: 304.44/291.49 gen_empty:node4_0(0) <=> empty 304.44/291.49 gen_empty:node4_0(+(x, 1)) <=> node(empty, gen_empty:node4_0(x)) 304.44/291.49 gen_0':s5_0(0) <=> 0' 304.44/291.49 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 304.44/291.49 304.44/291.49 304.44/291.49 The following defined symbols remain to be analysed: 304.44/291.49 count 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (15) LowerBoundPropagationProof (FINISHED) 304.44/291.49 Propagated lower bound. 304.44/291.49 ---------------------------------------- 304.44/291.49 304.44/291.49 (16) 304.44/291.49 BOUNDS(n^2, INF) 304.44/291.52 EOF