4.38/2.08	WORST_CASE(Omega(n^1), O(n^1))
4.38/2.09	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
4.38/2.09	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.38/2.09	
4.38/2.09	
4.38/2.09	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(1, 4 + -1 * Arg_1) + max(1, 3 + -1 * Arg_0)).
4.38/2.09	
4.38/2.09	(0) CpxIntTrs
4.38/2.09	(1) Koat2 Proof [FINISHED, 334 ms]
4.38/2.09	(2) BOUNDS(1, max(1, 4 + -1 * Arg_1) + max(1, 3 + -1 * Arg_0))
4.38/2.09	(3) Loat Proof [FINISHED, 331 ms]
4.38/2.09	(4) BOUNDS(n^1, INF)
4.38/2.09	
4.38/2.09	
4.38/2.09	----------------------------------------
4.38/2.09	
4.38/2.09	(0)
4.38/2.09	Obligation:
4.38/2.09	Complexity Int TRS consisting of the following rules:
4.38/2.09	f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: 1 >= A
4.38/2.09	f2(A, B, C) -> Com_1(f2(1 + A, 1 + B, C)) :|: 2 >= B && A >= 2
4.38/2.09	f2(A, B, C) -> Com_1(f300(A, B, D)) :|: B >= 3 && A >= 2
4.38/2.09	f1(A, B, C) -> Com_1(f2(A, B, C)) :|: TRUE
4.38/2.09	
4.38/2.09	The start-symbols are:[f1_3]
4.38/2.09	
4.38/2.09	
4.38/2.09	----------------------------------------
4.38/2.09	
4.38/2.09	(1) Koat2 Proof (FINISHED)
4.38/2.09	YES( ?, 1+max([0, 3-Arg_1])+max([1, 3-Arg_0]) {O(n)})
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Initial Complexity Problem:
4.38/2.09	
4.38/2.09	  Start:  f1  
4.38/2.09	
4.38/2.09	  Program_Vars:  Arg_0, Arg_1, Arg_2  
4.38/2.09	
4.38/2.09	  Temp_Vars:  D  
4.38/2.09	
4.38/2.09	  Locations:  f1, f2, f300  
4.38/2.09	
4.38/2.09	  Transitions:
4.38/2.09	
4.38/2.09	  f1(Arg_0,Arg_1,Arg_2) -> f2(Arg_0,Arg_1,Arg_2):|:
4.38/2.09	
4.38/2.09	  f2(Arg_0,Arg_1,Arg_2) -> f2(1+Arg_0,1+Arg_1,Arg_2):|:Arg_0 <= 1
4.38/2.09	
4.38/2.09	  f2(Arg_0,Arg_1,Arg_2) -> f2(1+Arg_0,1+Arg_1,Arg_2):|:Arg_1 <= 2 && 2 <= Arg_0
4.38/2.09	
4.38/2.09	  f2(Arg_0,Arg_1,Arg_2) -> f300(Arg_0,Arg_1,D):|:3 <= Arg_1 && 2 <= Arg_0  
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Timebounds: 
4.38/2.09	
4.38/2.09	  Overall timebound: 1+max([0, 3-Arg_1])+max([1, 3-Arg_0]) {O(n)}
4.38/2.09	
4.38/2.09	  3: f1->f2: 1 {O(1)}
4.38/2.09	
4.38/2.09	  0: f2->f2: max([0, 2-Arg_0]) {O(n)}
4.38/2.09	
4.38/2.09	  1: f2->f2: max([0, 3-Arg_1]) {O(n)}
4.38/2.09	
4.38/2.09	  2: f2->f300: 1 {O(1)}
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Costbounds:
4.38/2.09	
4.38/2.09	  Overall costbound: 1+max([0, 3-Arg_1])+max([1, 3-Arg_0]) {O(n)}
4.38/2.09	
4.38/2.09	  3: f1->f2: 1 {O(1)}
4.38/2.09	
4.38/2.09	  0: f2->f2: max([0, 2-Arg_0]) {O(n)}
4.38/2.09	
4.38/2.09	  1: f2->f2: max([0, 3-Arg_1]) {O(n)}
4.38/2.09	
4.38/2.09	  2: f2->f300: 1 {O(1)}
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Sizebounds:
4.38/2.09	
4.38/2.09	`Lower:
4.38/2.09	
4.38/2.09	  3: f1->f2, Arg_0: Arg_0 {O(n)}
4.38/2.09	
4.38/2.09	  3: f1->f2, Arg_1: Arg_1 {O(n)}
4.38/2.09	
4.38/2.09	  3: f1->f2, Arg_2: Arg_2 {O(n)}
4.38/2.09	
4.38/2.09	  0: f2->f2, Arg_0: Arg_0 {O(n)}
4.38/2.09	
4.38/2.09	  0: f2->f2, Arg_1: Arg_1 {O(n)}
4.38/2.09	
4.38/2.09	  0: f2->f2, Arg_2: Arg_2 {O(n)}
4.38/2.09	
4.38/2.09	  1: f2->f2, Arg_0: 3 {O(1)}
4.38/2.09	
4.38/2.09	  1: f2->f2, Arg_1: Arg_1 {O(n)}
4.38/2.09	
4.38/2.09	  1: f2->f2, Arg_2: Arg_2 {O(n)}
4.38/2.09	
4.38/2.09	  2: f2->f300, Arg_0: 2 {O(1)}
4.38/2.09	
4.38/2.09	  2: f2->f300, Arg_1: 3 {O(1)}
4.38/2.09	
4.38/2.09	`Upper:
4.38/2.09	
4.38/2.09	  3: f1->f2, Arg_0: Arg_0 {O(n)}
4.38/2.09	
4.38/2.09	  3: f1->f2, Arg_1: Arg_1 {O(n)}
4.38/2.09	
4.38/2.09	  3: f1->f2, Arg_2: Arg_2 {O(n)}
4.38/2.09	
4.38/2.09	  0: f2->f2, Arg_0: 2 {O(1)}
4.38/2.09	
4.38/2.09	  0: f2->f2, Arg_1: Arg_1+max([0, 2-Arg_0]) {O(n)}
4.38/2.09	
4.38/2.09	  0: f2->f2, Arg_2: Arg_2 {O(n)}
4.38/2.09	
4.38/2.09	  1: f2->f2, Arg_0: max([2, Arg_0])+max([0, 3-Arg_1]) {O(n)}
4.38/2.09	
4.38/2.09	  1: f2->f2, Arg_1: 3 {O(1)}
4.38/2.09	
4.38/2.09	  1: f2->f2, Arg_2: Arg_2 {O(n)}
4.38/2.09	
4.38/2.09	  2: f2->f300, Arg_0: max([2, max([Arg_0, max([2, Arg_0])+max([0, 3-Arg_1])])]) {O(n)}
4.38/2.09	
4.38/2.09	  2: f2->f300, Arg_1: max([3, max([Arg_1, Arg_1+max([0, 2-Arg_0])])]) {O(n)}
4.38/2.09	
4.38/2.09	
4.38/2.09	----------------------------------------
4.38/2.09	
4.38/2.09	(2)
4.38/2.09	BOUNDS(1, max(1, 4 + -1 * Arg_1) + max(1, 3 + -1 * Arg_0))
4.38/2.09	
4.38/2.09	----------------------------------------
4.38/2.09	
4.38/2.09	(3) Loat Proof (FINISHED)
4.38/2.09	
4.38/2.09	
4.38/2.09	### Pre-processing the ITS problem ###
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Initial linear ITS problem
4.38/2.09	
4.38/2.09	   Start location: f1
4.38/2.09	
4.38/2.09	      0: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=A ], cost: 1
4.38/2.09	
4.38/2.09	      1: f2 -> f2 : A'=1+A, B'=1+B, [ 2>=B && A>=2 ], cost: 1
4.38/2.09	
4.38/2.09	      2: f2 -> f300 : C'=free, [ B>=3 && A>=2 ], cost: 1
4.38/2.09	
4.38/2.09	      3: f1 -> f2 : [], cost: 1
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Removed unreachable and leaf rules:
4.38/2.09	
4.38/2.09	   Start location: f1
4.38/2.09	
4.38/2.09	      0: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=A ], cost: 1
4.38/2.09	
4.38/2.09	      1: f2 -> f2 : A'=1+A, B'=1+B, [ 2>=B && A>=2 ], cost: 1
4.38/2.09	
4.38/2.09	      3: f1 -> f2 : [], cost: 1
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	### Simplification by acceleration and chaining ###
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Accelerating simple loops of location 0.
4.38/2.09	
4.38/2.09	   Accelerating the following rules:
4.38/2.09	
4.38/2.09	      0: f2 -> f2 : A'=1+A, B'=1+B, [ 1>=A ], cost: 1
4.38/2.09	
4.38/2.09	      1: f2 -> f2 : A'=1+A, B'=1+B, [ 2>=B && A>=2 ], cost: 1
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	   Accelerated rule 0 with metering function 2-A, yielding the new rule 4.
4.38/2.09	
4.38/2.09	   Accelerated rule 1 with metering function 3-B, yielding the new rule 5.
4.38/2.09	
4.38/2.09	   Removing the simple loops: 0 1.
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Accelerated all simple loops using metering functions (where possible):
4.38/2.09	
4.38/2.09	   Start location: f1
4.38/2.09	
4.38/2.09	      4: f2 -> f2 : A'=2, B'=2-A+B, [ 1>=A ], cost: 2-A
4.38/2.09	
4.38/2.09	      5: f2 -> f2 : A'=3+A-B, B'=3, [ 2>=B && A>=2 ], cost: 3-B
4.38/2.09	
4.38/2.09	      3: f1 -> f2 : [], cost: 1
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Chained accelerated rules (with incoming rules):
4.38/2.09	
4.38/2.09	   Start location: f1
4.38/2.09	
4.38/2.09	      3: f1 -> f2 : [], cost: 1
4.38/2.09	
4.38/2.09	      6: f1 -> f2 : A'=2, B'=2-A+B, [ 1>=A ], cost: 3-A
4.38/2.09	
4.38/2.09	      7: f1 -> f2 : A'=3+A-B, B'=3, [ 2>=B && A>=2 ], cost: 4-B
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Removed unreachable locations (and leaf rules with constant cost):
4.38/2.09	
4.38/2.09	   Start location: f1
4.38/2.09	
4.38/2.09	      6: f1 -> f2 : A'=2, B'=2-A+B, [ 1>=A ], cost: 3-A
4.38/2.09	
4.38/2.09	      7: f1 -> f2 : A'=3+A-B, B'=3, [ 2>=B && A>=2 ], cost: 4-B
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	### Computing asymptotic complexity ###
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Fully simplified ITS problem
4.38/2.09	
4.38/2.09	   Start location: f1
4.38/2.09	
4.38/2.09	      6: f1 -> f2 : A'=2, B'=2-A+B, [ 1>=A ], cost: 3-A
4.38/2.09	
4.38/2.09	      7: f1 -> f2 : A'=3+A-B, B'=3, [ 2>=B && A>=2 ], cost: 4-B
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Computing asymptotic complexity for rule 6
4.38/2.09	
4.38/2.09	   Solved the limit problem by the following transformations:
4.38/2.09	
4.38/2.09	      Created initial limit problem:
4.38/2.09	
4.38/2.09	      2-A (+/+!), 3-A (+) [not solved]
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	      removing all constraints (solved by SMT)
4.38/2.09	
4.38/2.09	      resulting limit problem: [solved]
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	      applying transformation rule (C) using substitution {A==-n}
4.38/2.09	
4.38/2.09	      resulting limit problem:
4.38/2.09	
4.38/2.09	      [solved]
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	   Solution:
4.38/2.09	
4.38/2.09	      A / -n
4.38/2.09	
4.38/2.09	   Resulting cost 3+n has complexity: Poly(n^1)
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Found new complexity Poly(n^1).
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	Obtained the following overall complexity (w.r.t. the length of the input n):
4.38/2.09	
4.38/2.09	   Complexity:  Poly(n^1)
4.38/2.09	
4.38/2.09	   Cpx degree:  1
4.38/2.09	
4.38/2.09	   Solved cost: 3+n
4.38/2.09	
4.38/2.09	   Rule cost:   3-A
4.38/2.09	
4.38/2.09	   Rule guard:  [ 1>=A ]
4.38/2.09	
4.38/2.09	
4.38/2.09	
4.38/2.09	WORST_CASE(Omega(n^1),?)
4.38/2.09	
4.38/2.09	
4.38/2.09	----------------------------------------
4.38/2.09	
4.38/2.09	(4)
4.38/2.09	BOUNDS(n^1, INF)
4.44/2.11	EOF