4.21/2.17	WORST_CASE(?, O(n^1))
4.21/2.18	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.21/2.18	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.21/2.18	
4.21/2.18	
4.21/2.18	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, max(3, 3 + 4 * Arg_0) + nat(8 * Arg_0)).
4.21/2.18	
4.21/2.18	(0) CpxIntTrs
4.21/2.18	(1) Koat2 Proof [FINISHED, 133 ms]
4.21/2.18	(2) BOUNDS(1, max(3, 3 + 4 * Arg_0) + nat(8 * Arg_0))
4.21/2.18	
4.21/2.18	
4.21/2.18	----------------------------------------
4.21/2.18	
4.21/2.18	(0)
4.21/2.18	Obligation:
4.21/2.18	Complexity Int TRS consisting of the following rules:
4.21/2.18	start(A) -> Com_1(a(A)) :|: A >= 1
4.21/2.18	start(A) -> Com_1(a(A)) :|: A >= 2
4.21/2.18	start(A) -> Com_1(a(A)) :|: A >= 4
4.21/2.18	a(A) -> Com_1(a(B)) :|: 2 * B >= 2 && A >= 2 * B && A <= 2 * B
4.21/2.18	a(A) -> Com_1(a(B)) :|: 2 * B >= 1 && A >= 2 * B + 1 && A <= 2 * B + 1
4.21/2.18	
4.21/2.18	The start-symbols are:[start_1]
4.21/2.18	
4.21/2.18	
4.21/2.18	----------------------------------------
4.21/2.18	
4.21/2.18	(1) Koat2 Proof (FINISHED)
4.21/2.18	YES( ?, 3+2*(2*max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])) {O(n)})
4.21/2.18	
4.21/2.18	
4.21/2.18	
4.21/2.18	Initial Complexity Problem:
4.21/2.18	
4.21/2.18	  Start:  start  
4.21/2.18	
4.21/2.18	  Program_Vars:  Arg_0  
4.21/2.18	
4.21/2.18	  Temp_Vars:  B  
4.21/2.18	
4.21/2.18	  Locations:  a, start  
4.21/2.18	
4.21/2.18	  Transitions:
4.21/2.18	
4.21/2.18	  a(Arg_0) -> a(B):|:2 <= (2)*B && Arg_0 <= (2)*B && (2)*B <= Arg_0
4.21/2.18	
4.21/2.18	  a(Arg_0) -> a(B):|:1 <= (2)*B && Arg_0 <= (2)*B+1 && (2)*B+1 <= Arg_0
4.21/2.18	
4.21/2.18	  start(Arg_0) -> a(Arg_0):|:1 <= Arg_0
4.21/2.18	
4.21/2.18	  start(Arg_0) -> a(Arg_0):|:2 <= Arg_0
4.21/2.18	
4.21/2.18	  start(Arg_0) -> a(Arg_0):|:4 <= Arg_0  
4.21/2.18	
4.21/2.18	
4.21/2.18	
4.21/2.18	Timebounds: 
4.21/2.18	
4.21/2.18	  Overall timebound: 3+2*(2*max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])) {O(n)}
4.21/2.18	
4.21/2.18	  3: a->a: 2*max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0]) {O(n)}
4.21/2.18	
4.21/2.18	  4: a->a: 2*max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0]) {O(n)}
4.21/2.18	
4.21/2.18	  0: start->a: 1 {O(1)}
4.21/2.18	
4.21/2.18	  1: start->a: 1 {O(1)}
4.21/2.18	
4.21/2.18	  2: start->a: 1 {O(1)}
4.21/2.18	
4.21/2.18	
4.21/2.18	
4.21/2.18	Costbounds:
4.21/2.18	
4.21/2.18	  Overall costbound: 3+2*(2*max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])) {O(n)}
4.21/2.18	
4.21/2.18	  3: a->a: 2*max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0]) {O(n)}
4.21/2.18	
4.21/2.18	  4: a->a: 2*max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0])+max([0, Arg_0]) {O(n)}
4.21/2.18	
4.21/2.18	  0: start->a: 1 {O(1)}
4.21/2.18	
4.21/2.18	  1: start->a: 1 {O(1)}
4.21/2.18	
4.21/2.18	  2: start->a: 1 {O(1)}
4.21/2.18	
4.21/2.18	
4.21/2.18	
4.21/2.18	Sizebounds:
4.21/2.18	
4.21/2.18	`Lower:
4.21/2.18	
4.21/2.18	  3: a->a, Arg_0: 1 {O(1)}
4.21/2.18	
4.21/2.18	  4: a->a, Arg_0: 1 {O(1)}
4.21/2.18	
4.21/2.18	  0: start->a, Arg_0: 1 {O(1)}
4.21/2.18	
4.21/2.18	  1: start->a, Arg_0: 2 {O(1)}
4.21/2.18	
4.21/2.18	  2: start->a, Arg_0: 4 {O(1)}
4.21/2.18	
4.21/2.18	`Upper:
4.21/2.18	
4.21/2.18	  0: start->a, Arg_0: Arg_0 {O(n)}
4.21/2.18	
4.21/2.18	  1: start->a, Arg_0: Arg_0 {O(n)}
4.21/2.18	
4.21/2.18	  2: start->a, Arg_0: Arg_0 {O(n)}
4.21/2.18	
4.21/2.18	
4.21/2.18	----------------------------------------
4.21/2.18	
4.21/2.18	(2)
4.21/2.18	BOUNDS(1, max(3, 3 + 4 * Arg_0) + nat(8 * Arg_0))
4.21/2.20	EOF