7.76/3.70	WORST_CASE(Omega(n^1), O(n^1))
8.01/3.71	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
8.01/3.71	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
8.01/3.71	
8.01/3.71	
8.01/3.71	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
8.01/3.71	
8.01/3.71	(0) CpxIntTrs
8.01/3.71	(1) Koat Proof [FINISHED, 208 ms]
8.01/3.71	(2) BOUNDS(1, n^1)
8.01/3.71	(3) Loat Proof [FINISHED, 1994 ms]
8.01/3.71	(4) BOUNDS(n^1, INF)
8.01/3.71	
8.01/3.71	
8.01/3.71	----------------------------------------
8.01/3.71	
8.01/3.71	(0)
8.01/3.71	Obligation:
8.01/3.71	Complexity Int TRS consisting of the following rules:
8.01/3.71	start(A, B, C, D, E, F) -> Com_1(m1(A, B, C, D, E, F)) :|: A >= 0 && B + A + 2 >= 2 * C && B >= A + 1 && 2 * C >= B + A && D >= 0 && E + 1 >= C && E + 1 <= C && F >= A && F <= A
8.01/3.71	m1(A, B, C, D, E, F) -> Com_1(m1(A, B, H, D, E, G)) :|: B >= 1 && D >= 0 && A >= E + 1 && B + 1 >= G && C + 1 >= H && H >= 1 + C && F + 1 >= G && G >= 1 + F
8.01/3.71	m1(A, B, C, D, E, F) -> Com_1(m1(H, B, C, D, E, G)) :|: B >= 1 && D >= 0 && B >= F && E + 1 >= H && C >= B + 1 && F + 1 >= G && G >= 1 + F && A + 1 >= H && H >= 1 + A
8.01/3.71	m1(A, B, C, D, E, F) -> Com_1(m1(A, B, H, D, E, G)) :|: B >= 1 && D >= 0 && B >= F && B + 1 >= H && E >= A && F + 1 >= G && G >= 1 + F && C + 1 >= H && H >= 1 + C
8.01/3.71	m1(A, B, C, D, E, F) -> Com_1(m1(H, B, C, D, E, G)) :|: B >= 1 && D >= 0 && B >= F && B >= C && E + 1 >= H && A + 1 >= H && H >= 1 + A && F + 1 >= G && G >= 1 + F
8.01/3.71	
8.01/3.71	The start-symbols are:[start_6]
8.01/3.71	
8.01/3.71	
8.01/3.71	----------------------------------------
8.01/3.71	
8.01/3.71	(1) Koat Proof (FINISHED)
8.01/3.71	YES(?, 4*ar_1 + 5)
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Initial complexity problem:
8.01/3.71	
8.01/3.71	1:	T:
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 0 /\ ar_1 + ar_0 + 2 >= 2*ar_2 /\ ar_1 >= ar_0 + 1 /\ 2*ar_2 >= ar_1 + ar_0 /\ ar_3 >= 0 /\ ar_4 + 1 = ar_2 /\ ar_5 = ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]
8.01/3.71	
8.01/3.71		start location:	koat_start
8.01/3.71	
8.01/3.71		leaf cost:	0
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Repeatedly propagating knowledge in problem 1 produces the following problem:
8.01/3.71	
8.01/3.71	2:	T:
8.01/3.71	
8.01/3.71			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 0 /\ ar_1 + ar_0 + 2 >= 2*ar_2 /\ ar_1 >= ar_0 + 1 /\ 2*ar_2 >= ar_1 + ar_0 /\ ar_3 >= 0 /\ ar_4 + 1 = ar_2 /\ ar_5 = ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: ?, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]
8.01/3.71	
8.01/3.71		start location:	koat_start
8.01/3.71	
8.01/3.71		leaf cost:	0
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	A polynomial rank function with
8.01/3.71	
8.01/3.71		Pol(start) = V_2 + 1
8.01/3.71	
8.01/3.71		Pol(m1) = V_2 - V_6 + 1
8.01/3.71	
8.01/3.71		Pol(koat_start) = V_2 + 1
8.01/3.71	
8.01/3.71	orients all transitions weakly and the transitions
8.01/3.71	
8.01/3.71		m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ]
8.01/3.71	
8.01/3.71		m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71		m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71		m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ]
8.01/3.71	
8.01/3.71	strictly and produces the following problem:
8.01/3.71	
8.01/3.71	3:	T:
8.01/3.71	
8.01/3.71			(Comp: 1, Cost: 1)           start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ ar_0 >= 0 /\ ar_1 + ar_0 + 2 >= 2*ar_2 /\ ar_1 >= ar_0 + 1 /\ 2*ar_2 >= ar_1 + ar_0 /\ ar_3 >= 0 /\ ar_4 + 1 = ar_2 /\ ar_5 = ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: ar_1 + 1, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_0 >= ar_4 + 1 /\ ar_1 >= ar_5 ]
8.01/3.71	
8.01/3.71			(Comp: ar_1 + 1, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_4 >= ar_0 /\ ar_2 >= ar_1 + 1 ]
8.01/3.71	
8.01/3.71			(Comp: ar_1 + 1, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0, ar_1, ar_2 + 1, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: ar_1 + 1, Cost: 1)    m1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(m1(ar_0 + 1, ar_1, ar_2, ar_3, ar_4, ar_5 + 1)) [ ar_1 >= 1 /\ ar_3 >= 0 /\ ar_1 >= ar_5 /\ ar_1 >= ar_2 /\ ar_4 >= ar_0 ]
8.01/3.71	
8.01/3.71			(Comp: 1, Cost: 0)           koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5) -> Com_1(start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5)) [ 0 <= 0 ]
8.01/3.71	
8.01/3.71		start location:	koat_start
8.01/3.71	
8.01/3.71		leaf cost:	0
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Complexity upper bound 4*ar_1 + 5
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Time: 0.197 sec (SMT: 0.177 sec)
8.01/3.71	
8.01/3.71	
8.01/3.71	----------------------------------------
8.01/3.71	
8.01/3.71	(2)
8.01/3.71	BOUNDS(1, n^1)
8.01/3.71	
8.01/3.71	----------------------------------------
8.01/3.71	
8.01/3.71	(3) Loat Proof (FINISHED)
8.01/3.71	
8.01/3.71	
8.01/3.71	### Pre-processing the ITS problem ###
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Initial linear ITS problem
8.01/3.71	
8.01/3.71	   Start location: start
8.01/3.71	
8.01/3.71	      0: start -> m1 : [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ], cost: 1
8.01/3.71	
8.01/3.71	      1: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && A>=1+E && B>=F ], cost: 1
8.01/3.71	
8.01/3.71	      2: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B ], cost: 1
8.01/3.71	
8.01/3.71	      3: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1
8.01/3.71	
8.01/3.71	      4: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	### Simplification by acceleration and chaining ###
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Accelerating simple loops of location 1.
8.01/3.71	
8.01/3.71	   Accelerating the following rules:
8.01/3.71	
8.01/3.71	      1: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && A>=1+E && B>=F ], cost: 1
8.01/3.71	
8.01/3.71	      2: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B ], cost: 1
8.01/3.71	
8.01/3.71	      3: m1 -> m1 : C'=1+C, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1
8.01/3.71	
8.01/3.71	      4: m1 -> m1 : A'=1+A, F'=1+F, [ B>=1 && D>=0 && B>=F && B>=C && E>=A ], cost: 1
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	   Accelerated rule 1 with metering function 1-F+B, yielding the new rule 5.
8.01/3.71	
8.01/3.71	   Accelerated rule 2 with backward acceleration, yielding the new rule 6.
8.01/3.71	
8.01/3.71	   Accelerated rule 2 with backward acceleration, yielding the new rule 7.
8.01/3.71	
8.01/3.71	   Accelerated rule 3 with backward acceleration, yielding the new rule 8.
8.01/3.71	
8.01/3.71	   Accelerated rule 3 with backward acceleration, yielding the new rule 9.
8.01/3.71	
8.01/3.71	   Accelerated rule 4 with backward acceleration, yielding the new rule 10.
8.01/3.71	
8.01/3.71	   Accelerated rule 4 with backward acceleration, yielding the new rule 11.
8.01/3.71	
8.01/3.71	   Removing the simple loops: 1 2 3 4.
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Accelerated all simple loops using metering functions (where possible):
8.01/3.71	
8.01/3.71	   Start location: start
8.01/3.71	
8.01/3.71	      0: start -> m1 : [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ], cost: 1
8.01/3.71	
8.01/3.71	      5: m1 -> m1 : C'=1-F+C+B, F'=1+B, [ B>=1 && D>=0 && A>=1+E && B>=F ], cost: 1-F+B
8.01/3.71	
8.01/3.71	      6: m1 -> m1 : A'=1-F+A+B, F'=1+B, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B && E>=-F+A+B ], cost: 1-F+B
8.01/3.71	
8.01/3.71	      7: m1 -> m1 : A'=1+E, F'=1+F-A+E, [ B>=1 && D>=0 && B>=F && E>=A && C>=1+B && B>=F-A+E ], cost: 1-A+E
8.01/3.71	
8.01/3.71	      8: m1 -> m1 : C'=1-F+C+B, F'=1+B, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && B>=-F+C+B ], cost: 1-F+B
8.01/3.71	
8.01/3.71	      9: m1 -> m1 : C'=1+B, F'=1+F-C+B, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 1-C+B
8.01/3.71	
8.01/3.71	     10: m1 -> m1 : A'=1-F+A+B, F'=1+B, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && E>=-F+A+B ], cost: 1-F+B
8.01/3.71	
8.01/3.71	     11: m1 -> m1 : A'=1+E, F'=1+F-A+E, [ B>=1 && D>=0 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 1-A+E
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Chained accelerated rules (with incoming rules):
8.01/3.71	
8.01/3.71	   Start location: start
8.01/3.71	
8.01/3.71	      0: start -> m1 : [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ], cost: 1
8.01/3.71	
8.01/3.71	     12: start -> m1 : C'=1+B, F'=1+F-C+B, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 2-C+B
8.01/3.71	
8.01/3.71	     13: start -> m1 : A'=1+E, F'=1+F-A+E, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 2-A+E
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Removed unreachable locations (and leaf rules with constant cost):
8.01/3.71	
8.01/3.71	   Start location: start
8.01/3.71	
8.01/3.71	     12: start -> m1 : C'=1+B, F'=1+F-C+B, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 2-C+B
8.01/3.71	
8.01/3.71	     13: start -> m1 : A'=1+E, F'=1+F-A+E, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 2-A+E
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	### Computing asymptotic complexity ###
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Fully simplified ITS problem
8.01/3.71	
8.01/3.71	   Start location: start
8.01/3.71	
8.01/3.71	     12: start -> m1 : C'=1+B, F'=1+F-C+B, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-C+B ], cost: 2-C+B
8.01/3.71	
8.01/3.71	     13: start -> m1 : A'=1+E, F'=1+F-A+E, [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A && B>=1 && B>=F && B>=C && E>=A && B>=F-A+E ], cost: 2-A+E
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Computing asymptotic complexity for rule 12
8.01/3.71	
8.01/3.71	   Solved the limit problem by the following transformations:
8.01/3.71	
8.01/3.71	      Created initial limit problem:
8.01/3.71	
8.01/3.71	      1+F-A (+/+!), 1+2*C-A-B (+/+!), 2-C+B (+), C-E (+/+!), 3-2*C+A+B (+/+!), 1-F+A (+/+!), 2-C+E (+/+!), 1+D (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved]
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	      applying transformation rule (C) using substitution {C==1+E}
8.01/3.71	
8.01/3.71	      resulting limit problem:
8.01/3.71	
8.01/3.71	      1 (+/+!), 1+F-A (+/+!), 1-F+A (+/+!), 1+D (+/+!), 1-E+B (+), 1+A-2*E+B (+/+!), 3-A+2*E-B (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved]
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	      applying transformation rule (C) using substitution {F==A}
8.01/3.71	
8.01/3.71	      resulting limit problem:
8.01/3.71	
8.01/3.71	      1 (+/+!), 1+D (+/+!), 1-E+B (+), 1+A-2*E+B (+/+!), 3-A+2*E-B (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved]
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	      applying transformation rule (B), deleting 1 (+/+!)
8.01/3.71	
8.01/3.71	      resulting limit problem:
8.01/3.71	
8.01/3.71	      1+D (+/+!), 1-E+B (+), 1+A-2*E+B (+/+!), 3-A+2*E-B (+/+!), -A+B (+/+!), 1+A (+/+!) [not solved]
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	      removing all constraints (solved by SMT)
8.01/3.71	
8.01/3.71	      resulting limit problem: [solved]
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	      applying transformation rule (C) using substitution {D==n,A==0,E==n,B==2*n}
8.01/3.71	
8.01/3.71	      resulting limit problem:
8.01/3.71	
8.01/3.71	      [solved]
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	   Solution:
8.01/3.71	
8.01/3.71	      F / 0
8.01/3.71	
8.01/3.71	      C / 1+n
8.01/3.71	
8.01/3.71	      D / n
8.01/3.71	
8.01/3.71	      A / 0
8.01/3.71	
8.01/3.71	      E / n
8.01/3.71	
8.01/3.71	      B / 2*n
8.01/3.71	
8.01/3.71	   Resulting cost 1+n has complexity: Poly(n^1)
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Found new complexity Poly(n^1).
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	Obtained the following overall complexity (w.r.t. the length of the input n):
8.01/3.71	
8.01/3.71	   Complexity:  Poly(n^1)
8.01/3.71	
8.01/3.71	   Cpx degree:  1
8.01/3.71	
8.01/3.71	   Solved cost: 1+n
8.01/3.71	
8.01/3.71	   Rule cost:   2-C+B
8.01/3.71	
8.01/3.71	   Rule guard:  [ A>=0 && 2+A+B>=2*C && B>=1+A && 2*C>=A+B && D>=0 && 1+E==C && F==A ]
8.01/3.71	
8.01/3.71	
8.01/3.71	
8.01/3.71	WORST_CASE(Omega(n^1),?)
8.01/3.71	
8.01/3.71	
8.01/3.71	----------------------------------------
8.01/3.71	
8.01/3.71	(4)
8.01/3.71	BOUNDS(n^1, INF)
8.01/3.72	EOF