7.37/3.40 WORST_CASE(Omega(n^1), O(n^1)) 7.37/3.41 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 7.37/3.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.37/3.41 7.37/3.41 7.37/3.41 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 7.37/3.41 7.37/3.41 (0) CpxIntTrs 7.37/3.41 (1) Koat Proof [FINISHED, 394 ms] 7.37/3.41 (2) BOUNDS(1, n^1) 7.37/3.41 (3) Loat Proof [FINISHED, 1592 ms] 7.37/3.41 (4) BOUNDS(n^1, INF) 7.37/3.41 7.37/3.41 7.37/3.41 ---------------------------------------- 7.37/3.41 7.37/3.41 (0) 7.37/3.41 Obligation: 7.37/3.41 Complexity Int TRS consisting of the following rules: 7.37/3.41 f0(A, B, C, D) -> Com_1(f4(0, B, C, D)) :|: TRUE 7.37/3.41 f4(A, B, C, D) -> Com_1(f8(A + 1, B, 0, D)) :|: B >= A + 1 7.37/3.41 f8(A, B, C, D) -> Com_1(f16(A, B, C, 0)) :|: B >= A + 1 7.37/3.41 f8(A, B, C, D) -> Com_1(f16(A, B, C, D)) :|: A >= B 7.37/3.41 f8(A, B, C, D) -> Com_1(f8(A + 1, B, C + 1, E)) :|: B >= A + 1 && 0 >= E + 1 7.37/3.41 f8(A, B, C, D) -> Com_1(f8(A + 1, B, C + 1, E)) :|: B >= A + 1 && E >= 1 7.37/3.41 f16(A, B, C, D) -> Com_1(f4(A, B, C, D)) :|: 0 >= C 7.37/3.41 f16(A, B, C, D) -> Com_1(f4(A - 1, B, C, D)) :|: C >= 1 7.37/3.41 f4(A, B, C, D) -> Com_1(f20(A, B, C, D)) :|: A >= B 7.37/3.41 7.37/3.41 The start-symbols are:[f0_4] 7.37/3.41 7.37/3.41 7.37/3.41 ---------------------------------------- 7.37/3.41 7.37/3.41 (1) Koat Proof (FINISHED) 7.37/3.41 YES(?, 17*ar_1 + 2) 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Initial complexity problem: 7.37/3.41 7.37/3.41 1: T: 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f0(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(0, ar_1, ar_2, ar_3)) 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f8(ar_0 + 1, ar_1, 0, ar_3)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2, ar_3) -> Com_1(f16(ar_0, ar_1, ar_2, 0)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2, ar_3) -> Com_1(f16(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2, ar_3) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1, e)) [ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2, ar_3) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1, e)) [ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2, ar_3) -> Com_1(f4(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2, ar_3) -> Com_1(f20(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 7.37/3.41 7.37/3.41 start location: koat_start 7.37/3.41 7.37/3.41 leaf cost: 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [ar_0, ar_1, ar_2]. 7.37/3.41 7.37/3.41 We thus obtain the following problem: 7.37/3.41 7.37/3.41 2: T: 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f0(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f20(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0 - 1, ar_1, ar_2)) [ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, 0)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f0(ar_0, ar_1, ar_2) -> Com_1(f4(0, ar_1, ar_2)) 7.37/3.41 7.37/3.41 start location: koat_start 7.37/3.41 7.37/3.41 leaf cost: 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Repeatedly propagating knowledge in problem 2 produces the following problem: 7.37/3.41 7.37/3.41 3: T: 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f0(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f20(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0 - 1, ar_1, ar_2)) [ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, 0)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2) -> Com_1(f4(0, ar_1, ar_2)) 7.37/3.41 7.37/3.41 start location: koat_start 7.37/3.41 7.37/3.41 leaf cost: 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 A polynomial rank function with 7.37/3.41 7.37/3.41 Pol(koat_start) = 1 7.37/3.41 7.37/3.41 Pol(f0) = 1 7.37/3.41 7.37/3.41 Pol(f4) = 1 7.37/3.41 7.37/3.41 Pol(f20) = 0 7.37/3.41 7.37/3.41 Pol(f16) = 1 7.37/3.41 7.37/3.41 Pol(f8) = 1 7.37/3.41 7.37/3.41 orients all transitions weakly and the transition 7.37/3.41 7.37/3.41 f4(ar_0, ar_1, ar_2) -> Com_1(f20(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 strictly and produces the following problem: 7.37/3.41 7.37/3.41 4: T: 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f0(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f20(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0 - 1, ar_1, ar_2)) [ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, 0)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2) -> Com_1(f4(0, ar_1, ar_2)) 7.37/3.41 7.37/3.41 start location: koat_start 7.37/3.41 7.37/3.41 leaf cost: 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 A polynomial rank function with 7.37/3.41 7.37/3.41 Pol(koat_start) = V_2 7.37/3.41 7.37/3.41 Pol(f0) = V_2 7.37/3.41 7.37/3.41 Pol(f4) = -V_1 + V_2 7.37/3.41 7.37/3.41 Pol(f20) = -V_1 + V_2 7.37/3.41 7.37/3.41 Pol(f16) = -V_1 + V_2 + 1 7.37/3.41 7.37/3.41 Pol(f8) = -V_1 + V_2 + 1 7.37/3.41 7.37/3.41 orients all transitions weakly and the transitions 7.37/3.41 7.37/3.41 f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 strictly and produces the following problem: 7.37/3.41 7.37/3.41 5: T: 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f0(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f20(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0 - 1, ar_1, ar_2)) [ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 (Comp: ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, 0)) [ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2) -> Com_1(f4(0, ar_1, ar_2)) 7.37/3.41 7.37/3.41 start location: koat_start 7.37/3.41 7.37/3.41 leaf cost: 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Applied AI with 'oct' on problem 5 to obtain the following invariants: 7.37/3.41 7.37/3.41 For symbol f16: X_2 - X_3 - 1 >= 0 /\ X_1 - X_3 - 1 >= 0 /\ X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ -X_1 + X_2 >= 0 /\ X_1 - 1 >= 0 7.37/3.41 7.37/3.41 For symbol f4: X_1 >= 0 7.37/3.41 7.37/3.41 For symbol f8: X_2 - X_3 - 1 >= 0 /\ X_1 - X_3 - 1 >= 0 /\ X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ -X_1 + X_2 >= 0 /\ X_1 - 1 >= 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 This yielded the following problem: 7.37/3.41 7.37/3.41 6: T: 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2) -> Com_1(f4(0, ar_1, ar_2)) 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, 0)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 (Comp: ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 (Comp: ?, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0 - 1, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f20(ar_0, ar_1, ar_2)) [ ar_0 >= 0 /\ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f0(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 7.37/3.41 7.37/3.41 start location: koat_start 7.37/3.41 7.37/3.41 leaf cost: 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 A polynomial rank function with 7.37/3.41 7.37/3.41 Pol(f0) = 3*V_2 7.37/3.41 7.37/3.41 Pol(f4) = -3*V_1 + 3*V_2 7.37/3.41 7.37/3.41 Pol(f8) = -3*V_1 + 3*V_2 + 3*V_3 + 2 7.37/3.41 7.37/3.41 Pol(f16) = -3*V_1 + 3*V_2 + 3*V_3 + 1 7.37/3.41 7.37/3.41 Pol(f20) = -3*V_1 + 3*V_2 7.37/3.41 7.37/3.41 Pol(koat_start) = 3*V_2 7.37/3.41 7.37/3.41 orients all transitions weakly and the transitions 7.37/3.41 7.37/3.41 f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 f4(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, 0)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0 - 1, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 strictly and produces the following problem: 7.37/3.41 7.37/3.41 7: T: 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f0(ar_0, ar_1, ar_2) -> Com_1(f4(0, ar_1, ar_2)) 7.37/3.41 7.37/3.41 (Comp: 3*ar_1, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, 0)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: 3*ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 + 1 ] 7.37/3.41 7.37/3.41 (Comp: 3*ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f16(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 + 1 /\ 0 >= e + 1 ] 7.37/3.41 7.37/3.41 (Comp: ar_1, Cost: 1) f8(ar_0, ar_1, ar_2) -> Com_1(f8(ar_0 + 1, ar_1, ar_2 + 1)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_0 + 1 /\ e >= 1 ] 7.37/3.41 7.37/3.41 (Comp: 3*ar_1, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= ar_2 ] 7.37/3.41 7.37/3.41 (Comp: 3*ar_1, Cost: 1) f16(ar_0, ar_1, ar_2) -> Com_1(f4(ar_0 - 1, ar_1, ar_2)) [ ar_1 - ar_2 - 1 >= 0 /\ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ -ar_0 + ar_1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= 1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 1) f4(ar_0, ar_1, ar_2) -> Com_1(f20(ar_0, ar_1, ar_2)) [ ar_0 >= 0 /\ ar_0 >= ar_1 ] 7.37/3.41 7.37/3.41 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(f0(ar_0, ar_1, ar_2)) [ 0 <= 0 ] 7.37/3.41 7.37/3.41 start location: koat_start 7.37/3.41 7.37/3.41 leaf cost: 0 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Complexity upper bound 17*ar_1 + 2 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Time: 0.405 sec (SMT: 0.339 sec) 7.37/3.41 7.37/3.41 7.37/3.41 ---------------------------------------- 7.37/3.41 7.37/3.41 (2) 7.37/3.41 BOUNDS(1, n^1) 7.37/3.41 7.37/3.41 ---------------------------------------- 7.37/3.41 7.37/3.41 (3) Loat Proof (FINISHED) 7.37/3.41 7.37/3.41 7.37/3.41 ### Pre-processing the ITS problem ### 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Initial linear ITS problem 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 1: f4 -> f8 : A'=1+A, C'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 8: f4 -> f20 : [ A>=B ], cost: 1 7.37/3.41 7.37/3.41 2: f8 -> f16 : D'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 3: f8 -> f16 : [ A>=B ], cost: 1 7.37/3.41 7.37/3.41 4: f8 -> f8 : A'=1+A, C'=1+C, D'=free, [ B>=1+A && 0>=1+free ], cost: 1 7.37/3.41 7.37/3.41 5: f8 -> f8 : A'=1+A, C'=1+C, D'=free_1, [ B>=1+A && free_1>=1 ], cost: 1 7.37/3.41 7.37/3.41 6: f16 -> f4 : [ 0>=C ], cost: 1 7.37/3.41 7.37/3.41 7: f16 -> f4 : A'=-1+A, [ C>=1 ], cost: 1 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Removed unreachable and leaf rules: 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 1: f4 -> f8 : A'=1+A, C'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 2: f8 -> f16 : D'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 3: f8 -> f16 : [ A>=B ], cost: 1 7.37/3.41 7.37/3.41 4: f8 -> f8 : A'=1+A, C'=1+C, D'=free, [ B>=1+A && 0>=1+free ], cost: 1 7.37/3.41 7.37/3.41 5: f8 -> f8 : A'=1+A, C'=1+C, D'=free_1, [ B>=1+A && free_1>=1 ], cost: 1 7.37/3.41 7.37/3.41 6: f16 -> f4 : [ 0>=C ], cost: 1 7.37/3.41 7.37/3.41 7: f16 -> f4 : A'=-1+A, [ C>=1 ], cost: 1 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 ### Simplification by acceleration and chaining ### 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Accelerating simple loops of location 2. 7.37/3.41 7.37/3.41 Accelerating the following rules: 7.37/3.41 7.37/3.41 4: f8 -> f8 : A'=1+A, C'=1+C, D'=free, [ B>=1+A && 0>=1+free ], cost: 1 7.37/3.41 7.37/3.41 5: f8 -> f8 : A'=1+A, C'=1+C, D'=free_1, [ B>=1+A && free_1>=1 ], cost: 1 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Accelerated rule 4 with metering function -A+B, yielding the new rule 9. 7.37/3.41 7.37/3.41 Accelerated rule 5 with metering function -A+B, yielding the new rule 10. 7.37/3.41 7.37/3.41 Removing the simple loops: 4 5. 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Accelerated all simple loops using metering functions (where possible): 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 1: f4 -> f8 : A'=1+A, C'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 2: f8 -> f16 : D'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 3: f8 -> f16 : [ A>=B ], cost: 1 7.37/3.41 7.37/3.41 9: f8 -> f8 : A'=B, C'=C-A+B, D'=free, [ B>=1+A && 0>=1+free ], cost: -A+B 7.37/3.41 7.37/3.41 10: f8 -> f8 : A'=B, C'=C-A+B, D'=free_1, [ B>=1+A && free_1>=1 ], cost: -A+B 7.37/3.41 7.37/3.41 6: f16 -> f4 : [ 0>=C ], cost: 1 7.37/3.41 7.37/3.41 7: f16 -> f4 : A'=-1+A, [ C>=1 ], cost: 1 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Chained accelerated rules (with incoming rules): 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 1: f4 -> f8 : A'=1+A, C'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 11: f4 -> f8 : A'=B, C'=-1-A+B, D'=free, [ B>=2+A && 0>=1+free ], cost: -A+B 7.37/3.41 7.37/3.41 12: f4 -> f8 : A'=B, C'=-1-A+B, D'=free_1, [ B>=2+A && free_1>=1 ], cost: -A+B 7.37/3.41 7.37/3.41 2: f8 -> f16 : D'=0, [ B>=1+A ], cost: 1 7.37/3.41 7.37/3.41 3: f8 -> f16 : [ A>=B ], cost: 1 7.37/3.41 7.37/3.41 6: f16 -> f4 : [ 0>=C ], cost: 1 7.37/3.41 7.37/3.41 7: f16 -> f4 : A'=-1+A, [ C>=1 ], cost: 1 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Eliminated locations (on tree-shaped paths): 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 13: f4 -> f16 : A'=1+A, C'=0, D'=0, [ B>=2+A ], cost: 2 7.37/3.41 7.37/3.41 14: f4 -> f16 : A'=1+A, C'=0, [ B>=1+A && 1+A>=B ], cost: 2 7.37/3.41 7.37/3.41 15: f4 -> f16 : A'=B, C'=-1-A+B, D'=free, [ B>=2+A && 0>=1+free ], cost: 1-A+B 7.37/3.41 7.37/3.41 16: f4 -> f16 : A'=B, C'=-1-A+B, D'=free_1, [ B>=2+A && free_1>=1 ], cost: 1-A+B 7.37/3.41 7.37/3.41 17: f4 -> [6] : [ B>=2+A && 0>=1+free ], cost: -A+B 7.37/3.41 7.37/3.41 18: f4 -> [6] : [ B>=2+A && free_1>=1 ], cost: -A+B 7.37/3.41 7.37/3.41 6: f16 -> f4 : [ 0>=C ], cost: 1 7.37/3.41 7.37/3.41 7: f16 -> f4 : A'=-1+A, [ C>=1 ], cost: 1 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Eliminated locations (on tree-shaped paths): 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 17: f4 -> [6] : [ B>=2+A && 0>=1+free ], cost: -A+B 7.37/3.41 7.37/3.41 18: f4 -> [6] : [ B>=2+A && free_1>=1 ], cost: -A+B 7.37/3.41 7.37/3.41 19: f4 -> f4 : A'=1+A, C'=0, D'=0, [ B>=2+A ], cost: 3 7.37/3.41 7.37/3.41 20: f4 -> f4 : A'=1+A, C'=0, [ B>=1+A && 1+A>=B ], cost: 3 7.37/3.41 7.37/3.41 21: f4 -> f4 : A'=-1+B, C'=-1-A+B, D'=free, [ B>=2+A && 0>=1+free ], cost: 2-A+B 7.37/3.41 7.37/3.41 22: f4 -> f4 : A'=-1+B, C'=-1-A+B, D'=free_1, [ B>=2+A && free_1>=1 ], cost: 2-A+B 7.37/3.41 7.37/3.41 23: f4 -> [7] : [ B>=2+A && 0>=1+free ], cost: 1-A+B 7.37/3.41 7.37/3.41 24: f4 -> [7] : [ B>=2+A && free_1>=1 ], cost: 1-A+B 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Accelerating simple loops of location 1. 7.37/3.41 7.37/3.41 Simplified some of the simple loops (and removed duplicate rules). 7.37/3.41 7.37/3.41 Accelerating the following rules: 7.37/3.41 7.37/3.41 19: f4 -> f4 : A'=1+A, C'=0, D'=0, [ B>=2+A ], cost: 3 7.37/3.41 7.37/3.41 20: f4 -> f4 : A'=1+A, C'=0, [ 1+A-B==0 ], cost: 3 7.37/3.41 7.37/3.41 21: f4 -> f4 : A'=-1+B, C'=-1-A+B, D'=free, [ B>=2+A && 0>=1+free ], cost: 2-A+B 7.37/3.41 7.37/3.41 22: f4 -> f4 : A'=-1+B, C'=-1-A+B, D'=free_1, [ B>=2+A && free_1>=1 ], cost: 2-A+B 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Accelerated rule 19 with metering function -1-A+B, yielding the new rule 25. 7.37/3.41 7.37/3.41 Accelerated rule 20 with metering function -A+B, yielding the new rule 26. 7.37/3.41 7.37/3.41 Found no metering function for rule 21. 7.37/3.41 7.37/3.41 Found no metering function for rule 22. 7.37/3.41 7.37/3.41 Removing the simple loops: 19 20. 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Accelerated all simple loops using metering functions (where possible): 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 17: f4 -> [6] : [ B>=2+A && 0>=1+free ], cost: -A+B 7.37/3.41 7.37/3.41 18: f4 -> [6] : [ B>=2+A && free_1>=1 ], cost: -A+B 7.37/3.41 7.37/3.41 21: f4 -> f4 : A'=-1+B, C'=-1-A+B, D'=free, [ B>=2+A && 0>=1+free ], cost: 2-A+B 7.37/3.41 7.37/3.41 22: f4 -> f4 : A'=-1+B, C'=-1-A+B, D'=free_1, [ B>=2+A && free_1>=1 ], cost: 2-A+B 7.37/3.41 7.37/3.41 23: f4 -> [7] : [ B>=2+A && 0>=1+free ], cost: 1-A+B 7.37/3.41 7.37/3.41 24: f4 -> [7] : [ B>=2+A && free_1>=1 ], cost: 1-A+B 7.37/3.41 7.37/3.41 25: f4 -> f4 : A'=-1+B, C'=0, D'=0, [ B>=2+A ], cost: -3-3*A+3*B 7.37/3.41 7.37/3.41 26: f4 -> f4 : A'=B, C'=0, [ 1+A-B==0 ], cost: -3*A+3*B 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Chained accelerated rules (with incoming rules): 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 0: f0 -> f4 : A'=0, [], cost: 1 7.37/3.41 7.37/3.41 27: f0 -> f4 : A'=-1+B, C'=-1+B, D'=free, [ B>=2 && 0>=1+free ], cost: 3+B 7.37/3.41 7.37/3.41 28: f0 -> f4 : A'=-1+B, C'=-1+B, D'=free_1, [ B>=2 && free_1>=1 ], cost: 3+B 7.37/3.41 7.37/3.41 29: f0 -> f4 : A'=-1+B, C'=0, D'=0, [ B>=2 ], cost: -2+3*B 7.37/3.41 7.37/3.41 30: f0 -> f4 : A'=B, C'=0, [ 1-B==0 ], cost: 1+3*B 7.37/3.41 7.37/3.41 17: f4 -> [6] : [ B>=2+A && 0>=1+free ], cost: -A+B 7.37/3.41 7.37/3.41 18: f4 -> [6] : [ B>=2+A && free_1>=1 ], cost: -A+B 7.37/3.41 7.37/3.41 23: f4 -> [7] : [ B>=2+A && 0>=1+free ], cost: 1-A+B 7.37/3.41 7.37/3.41 24: f4 -> [7] : [ B>=2+A && free_1>=1 ], cost: 1-A+B 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Eliminated locations (on tree-shaped paths): 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 31: f0 -> [6] : A'=0, [ B>=2 && 0>=1+free ], cost: 1+B 7.37/3.41 7.37/3.41 32: f0 -> [6] : A'=0, [ B>=2 && free_1>=1 ], cost: 1+B 7.37/3.41 7.37/3.41 33: f0 -> [7] : A'=0, [ B>=2 && 0>=1+free ], cost: 2+B 7.37/3.41 7.37/3.41 34: f0 -> [7] : A'=0, [ B>=2 && free_1>=1 ], cost: 2+B 7.37/3.41 7.37/3.41 35: f0 -> [9] : [ B>=2 && 0>=1+free ], cost: 3+B 7.37/3.41 7.37/3.41 36: f0 -> [9] : [ B>=2 && free_1>=1 ], cost: 3+B 7.37/3.41 7.37/3.41 37: f0 -> [9] : [ B>=2 ], cost: -2+3*B 7.37/3.41 7.37/3.41 38: f0 -> [9] : [ 1-B==0 ], cost: 1+3*B 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 ### Computing asymptotic complexity ### 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Fully simplified ITS problem 7.37/3.41 7.37/3.41 Start location: f0 7.37/3.41 7.37/3.41 35: f0 -> [9] : [ B>=2 && 0>=1+free ], cost: 3+B 7.37/3.41 7.37/3.41 36: f0 -> [9] : [ B>=2 && free_1>=1 ], cost: 3+B 7.37/3.41 7.37/3.41 37: f0 -> [9] : [ B>=2 ], cost: -2+3*B 7.37/3.41 7.37/3.41 38: f0 -> [9] : [ 1-B==0 ], cost: 1+3*B 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Computing asymptotic complexity for rule 35 7.37/3.41 7.37/3.41 Solved the limit problem by the following transformations: 7.37/3.41 7.37/3.41 Created initial limit problem: 7.37/3.41 7.37/3.41 3+B (+), -1+B (+/+!), -free (+/+!) [not solved] 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 removing all constraints (solved by SMT) 7.37/3.41 7.37/3.41 resulting limit problem: [solved] 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 applying transformation rule (C) using substitution {free==-n,B==n} 7.37/3.41 7.37/3.41 resulting limit problem: 7.37/3.41 7.37/3.41 [solved] 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Solution: 7.37/3.41 7.37/3.41 free / -n 7.37/3.41 7.37/3.41 B / n 7.37/3.41 7.37/3.41 Resulting cost 3+n has complexity: Poly(n^1) 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Found new complexity Poly(n^1). 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 Obtained the following overall complexity (w.r.t. the length of the input n): 7.37/3.41 7.37/3.41 Complexity: Poly(n^1) 7.37/3.41 7.37/3.41 Cpx degree: 1 7.37/3.41 7.37/3.41 Solved cost: 3+n 7.37/3.41 7.37/3.41 Rule cost: 3+B 7.37/3.41 7.37/3.41 Rule guard: [ B>=2 && 0>=1+free ] 7.37/3.41 7.37/3.41 7.37/3.41 7.37/3.41 WORST_CASE(Omega(n^1),?) 7.37/3.41 7.37/3.41 7.37/3.41 ---------------------------------------- 7.37/3.41 7.37/3.41 (4) 7.37/3.41 BOUNDS(n^1, INF) 7.37/3.43 EOF