1135.12/291.58 WORST_CASE(Omega(n^2), ?) 1135.41/291.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1135.41/291.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1135.41/291.61 1135.41/291.61 1135.41/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1135.41/291.61 1135.41/291.61 (0) CpxTRS 1135.41/291.61 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1135.41/291.61 (2) CpxTRS 1135.41/291.61 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1135.41/291.61 (4) typed CpxTrs 1135.41/291.61 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1135.41/291.61 (6) typed CpxTrs 1135.41/291.61 (7) RewriteLemmaProof [LOWER BOUND(ID), 280 ms] 1135.41/291.61 (8) BEST 1135.41/291.61 (9) proven lower bound 1135.41/291.61 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1135.41/291.61 (11) BOUNDS(n^1, INF) 1135.41/291.61 (12) typed CpxTrs 1135.41/291.61 (13) RewriteLemmaProof [LOWER BOUND(ID), 50 ms] 1135.41/291.61 (14) BEST 1135.41/291.61 (15) proven lower bound 1135.41/291.61 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1135.41/291.61 (17) BOUNDS(n^2, INF) 1135.41/291.61 (18) typed CpxTrs 1135.41/291.61 (19) RewriteLemmaProof [LOWER BOUND(ID), 66 ms] 1135.41/291.61 (20) typed CpxTrs 1135.41/291.61 (21) RewriteLemmaProof [LOWER BOUND(ID), 2394 ms] 1135.41/291.61 (22) BOUNDS(1, INF) 1135.41/291.61 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (0) 1135.41/291.61 Obligation: 1135.41/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1135.41/291.61 1135.41/291.61 1135.41/291.61 The TRS R consists of the following rules: 1135.41/291.61 1135.41/291.61 plus(x, 0) -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0, y) -> 0 1135.41/291.61 times(x, 0) -> 0 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0)) -> 0 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 S is empty. 1135.41/291.61 Rewrite Strategy: INNERMOST 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1135.41/291.61 Renamed function symbols to avoid clashes with predefined symbol. 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (2) 1135.41/291.61 Obligation: 1135.41/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1135.41/291.61 1135.41/291.61 1135.41/291.61 The TRS R consists of the following rules: 1135.41/291.61 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 S is empty. 1135.41/291.61 Rewrite Strategy: INNERMOST 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1135.41/291.61 Infered types. 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (4) 1135.41/291.61 Obligation: 1135.41/291.61 Innermost TRS: 1135.41/291.61 Rules: 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 Types: 1135.41/291.61 plus :: 0':s -> 0':s -> 0':s 1135.41/291.61 0' :: 0':s 1135.41/291.61 s :: 0':s -> 0':s 1135.41/291.61 times :: 0':s -> 0':s -> 0':s 1135.41/291.61 p :: 0':s -> 0':s 1135.41/291.61 fac :: 0':s -> 0':s 1135.41/291.61 hole_0':s1_0 :: 0':s 1135.41/291.61 gen_0':s2_0 :: Nat -> 0':s 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (5) OrderProof (LOWER BOUND(ID)) 1135.41/291.61 Heuristically decided to analyse the following defined symbols: 1135.41/291.61 plus, times, p, fac 1135.41/291.61 1135.41/291.61 They will be analysed ascendingly in the following order: 1135.41/291.61 plus < times 1135.41/291.61 times < fac 1135.41/291.61 p < fac 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (6) 1135.41/291.61 Obligation: 1135.41/291.61 Innermost TRS: 1135.41/291.61 Rules: 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 Types: 1135.41/291.61 plus :: 0':s -> 0':s -> 0':s 1135.41/291.61 0' :: 0':s 1135.41/291.61 s :: 0':s -> 0':s 1135.41/291.61 times :: 0':s -> 0':s -> 0':s 1135.41/291.61 p :: 0':s -> 0':s 1135.41/291.61 fac :: 0':s -> 0':s 1135.41/291.61 hole_0':s1_0 :: 0':s 1135.41/291.61 gen_0':s2_0 :: Nat -> 0':s 1135.41/291.61 1135.41/291.61 1135.41/291.61 Generator Equations: 1135.41/291.61 gen_0':s2_0(0) <=> 0' 1135.41/291.61 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 1135.41/291.61 1135.41/291.61 1135.41/291.61 The following defined symbols remain to be analysed: 1135.41/291.61 plus, times, p, fac 1135.41/291.61 1135.41/291.61 They will be analysed ascendingly in the following order: 1135.41/291.61 plus < times 1135.41/291.61 times < fac 1135.41/291.61 p < fac 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1135.41/291.61 Proved the following rewrite lemma: 1135.41/291.61 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 1135.41/291.61 1135.41/291.61 Induction Base: 1135.41/291.61 plus(gen_0':s2_0(a), gen_0':s2_0(0)) ->_R^Omega(1) 1135.41/291.61 gen_0':s2_0(a) 1135.41/291.61 1135.41/291.61 Induction Step: 1135.41/291.61 plus(gen_0':s2_0(a), gen_0':s2_0(+(n4_0, 1))) ->_R^Omega(1) 1135.41/291.61 s(plus(gen_0':s2_0(a), gen_0':s2_0(n4_0))) ->_IH 1135.41/291.61 s(gen_0':s2_0(+(a, c5_0))) 1135.41/291.61 1135.41/291.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (8) 1135.41/291.61 Complex Obligation (BEST) 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (9) 1135.41/291.61 Obligation: 1135.41/291.61 Proved the lower bound n^1 for the following obligation: 1135.41/291.61 1135.41/291.61 Innermost TRS: 1135.41/291.61 Rules: 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 Types: 1135.41/291.61 plus :: 0':s -> 0':s -> 0':s 1135.41/291.61 0' :: 0':s 1135.41/291.61 s :: 0':s -> 0':s 1135.41/291.61 times :: 0':s -> 0':s -> 0':s 1135.41/291.61 p :: 0':s -> 0':s 1135.41/291.61 fac :: 0':s -> 0':s 1135.41/291.61 hole_0':s1_0 :: 0':s 1135.41/291.61 gen_0':s2_0 :: Nat -> 0':s 1135.41/291.61 1135.41/291.61 1135.41/291.61 Generator Equations: 1135.41/291.61 gen_0':s2_0(0) <=> 0' 1135.41/291.61 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 1135.41/291.61 1135.41/291.61 1135.41/291.61 The following defined symbols remain to be analysed: 1135.41/291.61 plus, times, p, fac 1135.41/291.61 1135.41/291.61 They will be analysed ascendingly in the following order: 1135.41/291.61 plus < times 1135.41/291.61 times < fac 1135.41/291.61 p < fac 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (10) LowerBoundPropagationProof (FINISHED) 1135.41/291.61 Propagated lower bound. 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (11) 1135.41/291.61 BOUNDS(n^1, INF) 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (12) 1135.41/291.61 Obligation: 1135.41/291.61 Innermost TRS: 1135.41/291.61 Rules: 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 Types: 1135.41/291.61 plus :: 0':s -> 0':s -> 0':s 1135.41/291.61 0' :: 0':s 1135.41/291.61 s :: 0':s -> 0':s 1135.41/291.61 times :: 0':s -> 0':s -> 0':s 1135.41/291.61 p :: 0':s -> 0':s 1135.41/291.61 fac :: 0':s -> 0':s 1135.41/291.61 hole_0':s1_0 :: 0':s 1135.41/291.61 gen_0':s2_0 :: Nat -> 0':s 1135.41/291.61 1135.41/291.61 1135.41/291.61 Lemmas: 1135.41/291.61 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 1135.41/291.61 1135.41/291.61 1135.41/291.61 Generator Equations: 1135.41/291.61 gen_0':s2_0(0) <=> 0' 1135.41/291.61 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 1135.41/291.61 1135.41/291.61 1135.41/291.61 The following defined symbols remain to be analysed: 1135.41/291.61 times, p, fac 1135.41/291.61 1135.41/291.61 They will be analysed ascendingly in the following order: 1135.41/291.61 times < fac 1135.41/291.61 p < fac 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1135.41/291.61 Proved the following rewrite lemma: 1135.41/291.61 times(gen_0':s2_0(n539_0), gen_0':s2_0(b)) -> gen_0':s2_0(*(n539_0, b)), rt in Omega(1 + b*n539_0 + n539_0) 1135.41/291.61 1135.41/291.61 Induction Base: 1135.41/291.61 times(gen_0':s2_0(0), gen_0':s2_0(b)) ->_R^Omega(1) 1135.41/291.61 0' 1135.41/291.61 1135.41/291.61 Induction Step: 1135.41/291.61 times(gen_0':s2_0(+(n539_0, 1)), gen_0':s2_0(b)) ->_R^Omega(1) 1135.41/291.61 plus(times(gen_0':s2_0(n539_0), gen_0':s2_0(b)), gen_0':s2_0(b)) ->_IH 1135.41/291.61 plus(gen_0':s2_0(*(c540_0, b)), gen_0':s2_0(b)) ->_L^Omega(1 + b) 1135.41/291.61 gen_0':s2_0(+(b, *(n539_0, b))) 1135.41/291.61 1135.41/291.61 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (14) 1135.41/291.61 Complex Obligation (BEST) 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (15) 1135.41/291.61 Obligation: 1135.41/291.61 Proved the lower bound n^2 for the following obligation: 1135.41/291.61 1135.41/291.61 Innermost TRS: 1135.41/291.61 Rules: 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 Types: 1135.41/291.61 plus :: 0':s -> 0':s -> 0':s 1135.41/291.61 0' :: 0':s 1135.41/291.61 s :: 0':s -> 0':s 1135.41/291.61 times :: 0':s -> 0':s -> 0':s 1135.41/291.61 p :: 0':s -> 0':s 1135.41/291.61 fac :: 0':s -> 0':s 1135.41/291.61 hole_0':s1_0 :: 0':s 1135.41/291.61 gen_0':s2_0 :: Nat -> 0':s 1135.41/291.61 1135.41/291.61 1135.41/291.61 Lemmas: 1135.41/291.61 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 1135.41/291.61 1135.41/291.61 1135.41/291.61 Generator Equations: 1135.41/291.61 gen_0':s2_0(0) <=> 0' 1135.41/291.61 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 1135.41/291.61 1135.41/291.61 1135.41/291.61 The following defined symbols remain to be analysed: 1135.41/291.61 times, p, fac 1135.41/291.61 1135.41/291.61 They will be analysed ascendingly in the following order: 1135.41/291.61 times < fac 1135.41/291.61 p < fac 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (16) LowerBoundPropagationProof (FINISHED) 1135.41/291.61 Propagated lower bound. 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (17) 1135.41/291.61 BOUNDS(n^2, INF) 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (18) 1135.41/291.61 Obligation: 1135.41/291.61 Innermost TRS: 1135.41/291.61 Rules: 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 Types: 1135.41/291.61 plus :: 0':s -> 0':s -> 0':s 1135.41/291.61 0' :: 0':s 1135.41/291.61 s :: 0':s -> 0':s 1135.41/291.61 times :: 0':s -> 0':s -> 0':s 1135.41/291.61 p :: 0':s -> 0':s 1135.41/291.61 fac :: 0':s -> 0':s 1135.41/291.61 hole_0':s1_0 :: 0':s 1135.41/291.61 gen_0':s2_0 :: Nat -> 0':s 1135.41/291.61 1135.41/291.61 1135.41/291.61 Lemmas: 1135.41/291.61 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 1135.41/291.61 times(gen_0':s2_0(n539_0), gen_0':s2_0(b)) -> gen_0':s2_0(*(n539_0, b)), rt in Omega(1 + b*n539_0 + n539_0) 1135.41/291.61 1135.41/291.61 1135.41/291.61 Generator Equations: 1135.41/291.61 gen_0':s2_0(0) <=> 0' 1135.41/291.61 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 1135.41/291.61 1135.41/291.61 1135.41/291.61 The following defined symbols remain to be analysed: 1135.41/291.61 p, fac 1135.41/291.61 1135.41/291.61 They will be analysed ascendingly in the following order: 1135.41/291.61 p < fac 1135.41/291.61 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1135.41/291.61 Proved the following rewrite lemma: 1135.41/291.61 p(gen_0':s2_0(+(1, n1228_0))) -> gen_0':s2_0(n1228_0), rt in Omega(1 + n1228_0) 1135.41/291.61 1135.41/291.61 Induction Base: 1135.41/291.61 p(gen_0':s2_0(+(1, 0))) ->_R^Omega(1) 1135.41/291.61 0' 1135.41/291.61 1135.41/291.61 Induction Step: 1135.41/291.61 p(gen_0':s2_0(+(1, +(n1228_0, 1)))) ->_R^Omega(1) 1135.41/291.61 s(p(s(gen_0':s2_0(n1228_0)))) ->_IH 1135.41/291.61 s(gen_0':s2_0(c1229_0)) 1135.41/291.61 1135.41/291.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (20) 1135.41/291.61 Obligation: 1135.41/291.61 Innermost TRS: 1135.41/291.61 Rules: 1135.41/291.61 plus(x, 0') -> x 1135.41/291.61 plus(x, s(y)) -> s(plus(x, y)) 1135.41/291.61 times(0', y) -> 0' 1135.41/291.61 times(x, 0') -> 0' 1135.41/291.61 times(s(x), y) -> plus(times(x, y), y) 1135.41/291.61 p(s(s(x))) -> s(p(s(x))) 1135.41/291.61 p(s(0')) -> 0' 1135.41/291.61 fac(s(x)) -> times(fac(p(s(x))), s(x)) 1135.41/291.61 1135.41/291.61 Types: 1135.41/291.61 plus :: 0':s -> 0':s -> 0':s 1135.41/291.61 0' :: 0':s 1135.41/291.61 s :: 0':s -> 0':s 1135.41/291.61 times :: 0':s -> 0':s -> 0':s 1135.41/291.61 p :: 0':s -> 0':s 1135.41/291.61 fac :: 0':s -> 0':s 1135.41/291.61 hole_0':s1_0 :: 0':s 1135.41/291.61 gen_0':s2_0 :: Nat -> 0':s 1135.41/291.61 1135.41/291.61 1135.41/291.61 Lemmas: 1135.41/291.61 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 1135.41/291.61 times(gen_0':s2_0(n539_0), gen_0':s2_0(b)) -> gen_0':s2_0(*(n539_0, b)), rt in Omega(1 + b*n539_0 + n539_0) 1135.41/291.61 p(gen_0':s2_0(+(1, n1228_0))) -> gen_0':s2_0(n1228_0), rt in Omega(1 + n1228_0) 1135.41/291.61 1135.41/291.61 1135.41/291.61 Generator Equations: 1135.41/291.61 gen_0':s2_0(0) <=> 0' 1135.41/291.61 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 1135.41/291.61 1135.41/291.61 1135.41/291.61 The following defined symbols remain to be analysed: 1135.41/291.61 fac 1135.41/291.61 ---------------------------------------- 1135.41/291.61 1135.41/291.61 (21) RewriteLemmaProof (LOWER BOUND(ID)) 1135.41/291.61 Proved the following rewrite lemma: 1135.41/291.61 fac(gen_0':s2_0(+(1, n1444_0))) -> *3_0, rt in Omega(n1444_0 + n1444_0^2) 1135.41/291.61 1135.41/291.61 Induction Base: 1135.41/291.62 fac(gen_0':s2_0(+(1, 0))) 1135.41/291.62 1135.41/291.62 Induction Step: 1135.41/291.62 fac(gen_0':s2_0(+(1, +(n1444_0, 1)))) ->_R^Omega(1) 1135.41/291.62 times(fac(p(s(gen_0':s2_0(+(1, n1444_0))))), s(gen_0':s2_0(+(1, n1444_0)))) ->_L^Omega(2 + n1444_0) 1135.41/291.62 times(fac(gen_0':s2_0(+(1, n1444_0))), s(gen_0':s2_0(+(1, n1444_0)))) ->_IH 1135.41/291.62 times(*3_0, s(gen_0':s2_0(+(1, n1444_0)))) 1135.41/291.62 1135.41/291.62 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1135.41/291.62 ---------------------------------------- 1135.41/291.62 1135.41/291.62 (22) 1135.41/291.62 BOUNDS(1, INF) 1135.58/291.71 EOF