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