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