5.64/2.68	WORST_CASE(?, O(n^2))
5.64/2.69	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.64/2.69	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.64/2.69	
5.64/2.69	
5.64/2.69	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, max(1, 1 + 3 * Arg_0) + nat(2 + 2 * Arg_0) + nat(3 * Arg_0 * max(1, Arg_0)) + nat(3 * Arg_0 * max(3 * Arg_0, 6)) + nat(Arg_0) + max(1, 1 + 2 * Arg_0) + max(5, 5 + 6 * Arg_0)).
5.64/2.69	
5.64/2.69	(0) CpxIntTrs
5.64/2.69	(1) Koat2 Proof [FINISHED, 1046 ms]
5.64/2.69	(2) BOUNDS(1, max(1, 1 + 3 * Arg_0) + nat(2 + 2 * Arg_0) + nat(3 * Arg_0 * max(1, Arg_0)) + nat(3 * Arg_0 * max(3 * Arg_0, 6)) + nat(Arg_0) + max(1, 1 + 2 * Arg_0) + max(5, 5 + 6 * Arg_0))
5.64/2.69	
5.64/2.69	
5.64/2.69	----------------------------------------
5.64/2.69	
5.64/2.69	(0)
5.64/2.69	Obligation:
5.64/2.69	Complexity Int TRS consisting of the following rules:
5.64/2.69	evalloopsstart(A, B) -> Com_1(evalloopsentryin(A, B)) :|: TRUE
5.64/2.69	evalloopsentryin(A, B) -> Com_1(evalloopsbb6in(A, B)) :|: A >= 0
5.64/2.69	evalloopsentryin(A, B) -> Com_1(evalloopsreturnin(A, B)) :|: 0 >= A + 1
5.64/2.69	evalloopsbb6in(A, B) -> Com_1(evalloopsbb1in(A, B)) :|: A >= 0
5.64/2.69	evalloopsbb6in(A, B) -> Com_1(evalloopsreturnin(A, B)) :|: 0 >= A + 1
5.64/2.69	evalloopsbb1in(A, B) -> Com_1(evalloopsbb4in(A, 1)) :|: A >= 2
5.64/2.69	evalloopsbb1in(A, B) -> Com_1(evalloopsbb5in(A, C)) :|: 1 >= A
5.64/2.69	evalloopsbb4in(A, B) -> Com_1(evalloopsbb3in(A, B)) :|: A >= B + 1
5.64/2.69	evalloopsbb4in(A, B) -> Com_1(evalloopsbb5in(A, B)) :|: B >= A
5.64/2.69	evalloopsbb3in(A, B) -> Com_1(evalloopsbb4in(A, 2 * B)) :|: TRUE
5.64/2.69	evalloopsbb5in(A, B) -> Com_1(evalloopsbb6in(A - 1, B)) :|: TRUE
5.64/2.69	evalloopsreturnin(A, B) -> Com_1(evalloopsstop(A, B)) :|: TRUE
5.64/2.69	
5.64/2.69	The start-symbols are:[evalloopsstart_2]
5.64/2.69	
5.64/2.69	
5.64/2.69	----------------------------------------
5.64/2.69	
5.64/2.69	(1) Koat2 Proof (FINISHED)
5.64/2.69	YES( ?, 5+2*max([0, 3*Arg_0])+max([1, 1+3*Arg_0])+max([0, 1+Arg_0])+max([0, 1+Arg_0])+max([0, 3*Arg_0*max([1, Arg_0])])+max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, Arg_0])+max([1, 1+2*Arg_0]) {O(n^2)})
5.64/2.69	
5.64/2.69	
5.64/2.69	
5.64/2.69	Initial Complexity Problem:
5.64/2.69	
5.64/2.69	  Start:  evalloopsstart  
5.64/2.69	
5.64/2.69	  Program_Vars:  Arg_0, Arg_1  
5.64/2.69	
5.64/2.69	  Temp_Vars:  C  
5.64/2.69	
5.64/2.69	  Locations:  evalloopsbb1in, evalloopsbb3in, evalloopsbb4in, evalloopsbb5in, evalloopsbb6in, evalloopsentryin, evalloopsreturnin, evalloopsstart, evalloopsstop  
5.64/2.69	
5.64/2.69	  Transitions:
5.64/2.69	
5.64/2.69	  evalloopsbb1in(Arg_0,Arg_1) -> evalloopsbb4in(Arg_0,1):|:0 <= Arg_0 && 2 <= Arg_0
5.64/2.69	
5.64/2.69	  evalloopsbb1in(Arg_0,Arg_1) -> evalloopsbb5in(Arg_0,C):|:0 <= Arg_0 && Arg_0 <= 1
5.64/2.69	
5.64/2.69	  evalloopsbb3in(Arg_0,Arg_1) -> evalloopsbb4in(Arg_0,(2)*Arg_1):|:1+Arg_1 <= Arg_0 && 1 <= Arg_1 && 3 <= Arg_0+Arg_1 && 2 <= Arg_0
5.64/2.69	
5.64/2.69	  evalloopsbb4in(Arg_0,Arg_1) -> evalloopsbb3in(Arg_0,Arg_1):|:1 <= Arg_1 && 3 <= Arg_0+Arg_1 && 2 <= Arg_0 && Arg_1+1 <= Arg_0
5.64/2.69	
5.64/2.69	  evalloopsbb4in(Arg_0,Arg_1) -> evalloopsbb5in(Arg_0,Arg_1):|:1 <= Arg_1 && 3 <= Arg_0+Arg_1 && 2 <= Arg_0 && Arg_0 <= Arg_1
5.64/2.69	
5.64/2.69	  evalloopsbb5in(Arg_0,Arg_1) -> evalloopsbb6in(Arg_0-1,Arg_1):|:0 <= Arg_0
5.64/2.69	
5.64/2.69	  evalloopsbb6in(Arg_0,Arg_1) -> evalloopsbb1in(Arg_0,Arg_1):|:0 <= Arg_0
5.64/2.69	
5.64/2.69	  evalloopsbb6in(Arg_0,Arg_1) -> evalloopsreturnin(Arg_0,Arg_1):|:Arg_0+1 <= 0
5.64/2.69	
5.64/2.69	  evalloopsentryin(Arg_0,Arg_1) -> evalloopsbb6in(Arg_0,Arg_1):|:0 <= Arg_0
5.64/2.69	
5.64/2.69	  evalloopsentryin(Arg_0,Arg_1) -> evalloopsreturnin(Arg_0,Arg_1):|:Arg_0+1 <= 0
5.64/2.69	
5.64/2.69	  evalloopsreturnin(Arg_0,Arg_1) -> evalloopsstop(Arg_0,Arg_1):|:1+Arg_0 <= 0
5.64/2.69	
5.64/2.69	  evalloopsstart(Arg_0,Arg_1) -> evalloopsentryin(Arg_0,Arg_1):|:  
5.64/2.69	
5.64/2.69	
5.64/2.69	
5.64/2.69	Timebounds: 
5.64/2.69	
5.64/2.69	  Overall timebound: 5+2*max([0, 3*Arg_0])+max([1, 1+3*Arg_0])+max([0, 1+Arg_0])+max([0, 1+Arg_0])+max([0, 3*Arg_0*max([1, Arg_0])])+max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, Arg_0])+max([1, 1+2*Arg_0]) {O(n^2)}
5.64/2.69	
5.64/2.69	  5: evalloopsbb1in->evalloopsbb4in: max([0, 1+Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  6: evalloopsbb1in->evalloopsbb5in: max([1, 1+2*Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  9: evalloopsbb3in->evalloopsbb4in: max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0]) {O(n^2)}
5.64/2.69	
5.64/2.69	  7: evalloopsbb4in->evalloopsbb3in: max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, 3*Arg_0]) {O(n^2)}
5.64/2.69	
5.64/2.69	  8: evalloopsbb4in->evalloopsbb5in: max([0, 3*Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  10: evalloopsbb5in->evalloopsbb6in: max([0, 1+Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  3: evalloopsbb6in->evalloopsbb1in: max([1, 1+3*Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  4: evalloopsbb6in->evalloopsreturnin: 1 {O(1)}
5.64/2.69	
5.64/2.69	  1: evalloopsentryin->evalloopsbb6in: 1 {O(1)}
5.64/2.69	
5.64/2.69	  2: evalloopsentryin->evalloopsreturnin: 1 {O(1)}
5.64/2.69	
5.64/2.69	  11: evalloopsreturnin->evalloopsstop: 1 {O(1)}
5.64/2.69	
5.64/2.69	  0: evalloopsstart->evalloopsentryin: 1 {O(1)}
5.64/2.69	
5.64/2.69	
5.64/2.69	
5.64/2.69	Costbounds:
5.64/2.69	
5.64/2.69	  Overall costbound: 5+2*max([0, 3*Arg_0])+max([1, 1+3*Arg_0])+max([0, 1+Arg_0])+max([0, 1+Arg_0])+max([0, 3*Arg_0*max([1, Arg_0])])+max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, Arg_0])+max([1, 1+2*Arg_0]) {O(n^2)}
5.64/2.69	
5.64/2.69	  5: evalloopsbb1in->evalloopsbb4in: max([0, 1+Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  6: evalloopsbb1in->evalloopsbb5in: max([1, 1+2*Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  9: evalloopsbb3in->evalloopsbb4in: max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0]) {O(n^2)}
5.64/2.69	
5.64/2.69	  7: evalloopsbb4in->evalloopsbb3in: max([0, 3*Arg_0*max([6, 3*max([1, Arg_0])])])+max([0, 3*Arg_0]) {O(n^2)}
5.64/2.69	
5.64/2.69	  8: evalloopsbb4in->evalloopsbb5in: max([0, 3*Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  10: evalloopsbb5in->evalloopsbb6in: max([0, 1+Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  3: evalloopsbb6in->evalloopsbb1in: max([1, 1+3*Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  4: evalloopsbb6in->evalloopsreturnin: 1 {O(1)}
5.64/2.69	
5.64/2.69	  1: evalloopsentryin->evalloopsbb6in: 1 {O(1)}
5.64/2.69	
5.64/2.69	  2: evalloopsentryin->evalloopsreturnin: 1 {O(1)}
5.64/2.69	
5.64/2.69	  11: evalloopsreturnin->evalloopsstop: 1 {O(1)}
5.64/2.69	
5.64/2.69	  0: evalloopsstart->evalloopsentryin: 1 {O(1)}
5.64/2.69	
5.64/2.69	
5.64/2.69	
5.64/2.69	Sizebounds:
5.64/2.69	
5.64/2.69	`Lower:
5.64/2.69	
5.64/2.69	  5: evalloopsbb1in->evalloopsbb4in, Arg_0: 2 {O(1)}
5.64/2.69	
5.64/2.69	  5: evalloopsbb1in->evalloopsbb4in, Arg_1: 1 {O(1)}
5.64/2.69	
5.64/2.69	  6: evalloopsbb1in->evalloopsbb5in, Arg_0: 0 {O(1)}
5.64/2.69	
5.64/2.69	  9: evalloopsbb3in->evalloopsbb4in, Arg_0: 2 {O(1)}
5.64/2.69	
5.64/2.69	  9: evalloopsbb3in->evalloopsbb4in, Arg_1: 2 {O(1)}
5.64/2.69	
5.64/2.69	  7: evalloopsbb4in->evalloopsbb3in, Arg_0: 2 {O(1)}
5.64/2.69	
5.64/2.69	  7: evalloopsbb4in->evalloopsbb3in, Arg_1: 1 {O(1)}
5.64/2.69	
5.64/2.69	  8: evalloopsbb4in->evalloopsbb5in, Arg_0: 2 {O(1)}
5.64/2.69	
5.64/2.69	  8: evalloopsbb4in->evalloopsbb5in, Arg_1: 2 {O(1)}
5.64/2.69	
5.64/2.69	  10: evalloopsbb5in->evalloopsbb6in, Arg_0: -1 {O(1)}
5.64/2.69	
5.64/2.69	  3: evalloopsbb6in->evalloopsbb1in, Arg_0: 0 {O(1)}
5.64/2.69	
5.64/2.69	  4: evalloopsbb6in->evalloopsreturnin, Arg_0: -1 {O(1)}
5.64/2.69	
5.64/2.69	  1: evalloopsentryin->evalloopsbb6in, Arg_0: 0 {O(1)}
5.64/2.69	
5.64/2.69	  1: evalloopsentryin->evalloopsbb6in, Arg_1: Arg_1 {O(n)}
5.64/2.69	
5.64/2.69	  2: evalloopsentryin->evalloopsreturnin, Arg_0: Arg_0 {O(n)}
5.64/2.69	
5.64/2.69	  2: evalloopsentryin->evalloopsreturnin, Arg_1: Arg_1 {O(n)}
5.64/2.69	
5.64/2.69	  11: evalloopsreturnin->evalloopsstop, Arg_0: min([-1, Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  0: evalloopsstart->evalloopsentryin, Arg_0: Arg_0 {O(n)}
5.64/2.69	
5.64/2.69	  0: evalloopsstart->evalloopsentryin, Arg_1: Arg_1 {O(n)}
5.64/2.69	
5.64/2.69	`Upper:
5.64/2.69	
5.64/2.69	  5: evalloopsbb1in->evalloopsbb4in, Arg_0: max([1, Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  5: evalloopsbb1in->evalloopsbb4in, Arg_1: 1 {O(1)}
5.64/2.69	
5.64/2.69	  6: evalloopsbb1in->evalloopsbb5in, Arg_0: 1 {O(1)}
5.64/2.69	
5.64/2.69	  9: evalloopsbb3in->evalloopsbb4in, Arg_0: max([1, Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  9: evalloopsbb3in->evalloopsbb4in, Arg_1: 2^(max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0])) {O(EXP)}
5.64/2.69	
5.64/2.69	  7: evalloopsbb4in->evalloopsbb3in, Arg_0: max([1, Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  7: evalloopsbb4in->evalloopsbb3in, Arg_1: 2^(max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0])) {O(EXP)}
5.64/2.69	
5.64/2.69	  8: evalloopsbb4in->evalloopsbb5in, Arg_0: max([1, Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  8: evalloopsbb4in->evalloopsbb5in, Arg_1: 2^(max([0, 3*Arg_0*max([1, Arg_0])])+max([0, Arg_0])) {O(EXP)}
5.64/2.69	
5.64/2.69	  10: evalloopsbb5in->evalloopsbb6in, Arg_0: max([1, Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  3: evalloopsbb6in->evalloopsbb1in, Arg_0: max([1, Arg_0]) {O(n)}
5.64/2.69	
5.64/2.69	  4: evalloopsbb6in->evalloopsreturnin, Arg_0: -1 {O(1)}
5.64/2.69	
5.64/2.69	  1: evalloopsentryin->evalloopsbb6in, Arg_0: Arg_0 {O(n)}
5.64/2.69	
5.64/2.69	  1: evalloopsentryin->evalloopsbb6in, Arg_1: Arg_1 {O(n)}
5.64/2.69	
5.64/2.69	  2: evalloopsentryin->evalloopsreturnin, Arg_0: -1 {O(1)}
5.64/2.69	
5.64/2.69	  2: evalloopsentryin->evalloopsreturnin, Arg_1: Arg_1 {O(n)}
5.64/2.69	
5.64/2.69	  11: evalloopsreturnin->evalloopsstop, Arg_0: -1 {O(1)}
5.64/2.69	
5.64/2.69	  0: evalloopsstart->evalloopsentryin, Arg_0: Arg_0 {O(n)}
5.64/2.69	
5.64/2.69	  0: evalloopsstart->evalloopsentryin, Arg_1: Arg_1 {O(n)}
5.64/2.69	
5.64/2.69	
5.64/2.69	----------------------------------------
5.64/2.69	
5.64/2.69	(2)
5.64/2.69	BOUNDS(1, max(1, 1 + 3 * Arg_0) + nat(2 + 2 * Arg_0) + nat(3 * Arg_0 * max(1, Arg_0)) + nat(3 * Arg_0 * max(3 * Arg_0, 6)) + nat(Arg_0) + max(1, 1 + 2 * Arg_0) + max(5, 5 + 6 * Arg_0))
5.76/2.71	EOF