366.83/291.57	WORST_CASE(Omega(n^1), O(n^2))
366.87/291.59	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
366.87/291.59	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
366.87/291.59	
366.87/291.59	
366.87/291.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
366.87/291.59	
366.87/291.59	(0) CpxTRS
366.87/291.59	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
366.87/291.59	(2) CpxWeightedTrs
366.87/291.59	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
366.87/291.59	    (4) CpxTypedWeightedTrs
366.87/291.59	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
366.87/291.59	    (6) CpxTypedWeightedCompleteTrs
366.87/291.59	    (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
366.87/291.59	    (8) CpxTypedWeightedCompleteTrs
366.87/291.59	    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
366.87/291.59	    (10) CpxRNTS
366.87/291.59	    (11) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
366.87/291.59	    (12) CpxRNTS
366.87/291.59	    (13) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
366.87/291.59	    (14) CpxRNTS
366.87/291.59	    (15) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
366.87/291.59	    (16) CpxRNTS
366.87/291.59	    (17) IntTrsBoundProof [UPPER BOUND(ID), 265 ms]
366.87/291.59	    (18) CpxRNTS
366.87/291.59	    (19) IntTrsBoundProof [UPPER BOUND(ID), 109 ms]
366.87/291.59	    (20) CpxRNTS
366.87/291.59	    (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
366.87/291.59	    (22) CpxRNTS
366.87/291.59	    (23) IntTrsBoundProof [UPPER BOUND(ID), 190 ms]
366.87/291.59	    (24) CpxRNTS
366.87/291.59	    (25) IntTrsBoundProof [UPPER BOUND(ID), 55 ms]
366.87/291.59	    (26) CpxRNTS
366.87/291.59	    (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
366.87/291.59	    (28) CpxRNTS
366.87/291.59	    (29) IntTrsBoundProof [UPPER BOUND(ID), 402 ms]
366.87/291.59	    (30) CpxRNTS
366.87/291.59	    (31) IntTrsBoundProof [UPPER BOUND(ID), 164 ms]
366.87/291.59	    (32) CpxRNTS
366.87/291.59	    (33) FinalProof [FINISHED, 0 ms]
366.87/291.59	    (34) BOUNDS(1, n^2)
366.87/291.59	(35) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
366.87/291.59	(36) TRS for Loop Detection
366.87/291.59	    (37) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
366.87/291.59	    (38) BEST
366.87/291.59	        (39) proven lower bound
366.87/291.59	            (40) LowerBoundPropagationProof [FINISHED, 0 ms]
366.87/291.59	            (41) BOUNDS(n^1, INF)
366.87/291.59	        (42) TRS for Loop Detection
366.87/291.59	
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(0)
366.87/291.59	Obligation:
366.87/291.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
366.87/291.59	
366.87/291.59	
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, x) -> cond(odd(x), p(x))
366.87/291.59	   odd(0) -> false
366.87/291.59	   odd(s(0)) -> true
366.87/291.59	   odd(s(s(x))) -> odd(x)
366.87/291.59	   p(0) -> 0
366.87/291.59	   p(s(x)) -> x
366.87/291.59	
366.87/291.59	S is empty.
366.87/291.59	Rewrite Strategy: INNERMOST
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
366.87/291.59	Transformed relative TRS to weighted TRS
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(2)
366.87/291.59	Obligation:
366.87/291.59	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
366.87/291.59	
366.87/291.59	
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, x) -> cond(odd(x), p(x)) [1]
366.87/291.59	   odd(0) -> false [1]
366.87/291.59	   odd(s(0)) -> true [1]
366.87/291.59	   odd(s(s(x))) -> odd(x) [1]
366.87/291.59	   p(0) -> 0 [1]
366.87/291.59	   p(s(x)) -> x [1]
366.87/291.59	
366.87/291.59	Rewrite Strategy: INNERMOST
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
366.87/291.59	Infered types.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(4)
366.87/291.59	Obligation:
366.87/291.59	Runtime Complexity Weighted TRS with Types.
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, x) -> cond(odd(x), p(x)) [1]
366.87/291.59	   odd(0) -> false [1]
366.87/291.59	   odd(s(0)) -> true [1]
366.87/291.59	   odd(s(s(x))) -> odd(x) [1]
366.87/291.59	   p(0) -> 0 [1]
366.87/291.59	   p(s(x)) -> x [1]
366.87/291.59	
366.87/291.59	The TRS has the following type information:
366.87/291.59	cond :: true:false -> 0:s -> cond
366.87/291.59	true :: true:false
366.87/291.59	odd :: 0:s -> true:false
366.87/291.59	p :: 0:s -> 0:s
366.87/291.59	0 :: 0:s
366.87/291.59	false :: true:false
366.87/291.59	s :: 0:s -> 0:s
366.87/291.59	
366.87/291.59	Rewrite Strategy: INNERMOST
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(5) CompletionProof (UPPER BOUND(ID))
366.87/291.59	The transformation into a RNTS is sound, since:
366.87/291.59	
366.87/291.59	(a) The obligation is a constructor system where every type has a constant constructor,
366.87/291.59	
366.87/291.59	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
366.87/291.59	
366.87/291.59	   cond_2
366.87/291.59	
366.87/291.59	(c) The following functions are completely defined:
366.87/291.59	
366.87/291.59	   odd_1
366.87/291.59	   p_1
366.87/291.59	
366.87/291.59	Due to the following rules being added:
366.87/291.59	none
366.87/291.59	
366.87/291.59	And the following fresh constants:    const
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(6)
366.87/291.59	Obligation:
366.87/291.59	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
366.87/291.59	
366.87/291.59	Runtime Complexity Weighted TRS with Types.
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, x) -> cond(odd(x), p(x)) [1]
366.87/291.59	   odd(0) -> false [1]
366.87/291.59	   odd(s(0)) -> true [1]
366.87/291.59	   odd(s(s(x))) -> odd(x) [1]
366.87/291.59	   p(0) -> 0 [1]
366.87/291.59	   p(s(x)) -> x [1]
366.87/291.59	
366.87/291.59	The TRS has the following type information:
366.87/291.59	cond :: true:false -> 0:s -> cond
366.87/291.59	true :: true:false
366.87/291.59	odd :: 0:s -> true:false
366.87/291.59	p :: 0:s -> 0:s
366.87/291.59	0 :: 0:s
366.87/291.59	false :: true:false
366.87/291.59	s :: 0:s -> 0:s
366.87/291.59	const :: cond
366.87/291.59	
366.87/291.59	Rewrite Strategy: INNERMOST
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(7) NarrowingProof (BOTH BOUNDS(ID, ID))
366.87/291.59	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(8)
366.87/291.59	Obligation:
366.87/291.59	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
366.87/291.59	
366.87/291.59	Runtime Complexity Weighted TRS with Types.
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, 0) -> cond(false, 0) [3]
366.87/291.59	   cond(true, s(0)) -> cond(true, 0) [3]
366.87/291.59	   cond(true, s(s(x'))) -> cond(odd(x'), s(x')) [3]
366.87/291.59	   odd(0) -> false [1]
366.87/291.59	   odd(s(0)) -> true [1]
366.87/291.59	   odd(s(s(x))) -> odd(x) [1]
366.87/291.59	   p(0) -> 0 [1]
366.87/291.59	   p(s(x)) -> x [1]
366.87/291.59	
366.87/291.59	The TRS has the following type information:
366.87/291.59	cond :: true:false -> 0:s -> cond
366.87/291.59	true :: true:false
366.87/291.59	odd :: 0:s -> true:false
366.87/291.59	p :: 0:s -> 0:s
366.87/291.59	0 :: 0:s
366.87/291.59	false :: true:false
366.87/291.59	s :: 0:s -> 0:s
366.87/291.59	const :: cond
366.87/291.59	
366.87/291.59	Rewrite Strategy: INNERMOST
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
366.87/291.59	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
366.87/291.59	The constant constructors are abstracted as follows:
366.87/291.59	
366.87/291.59	   true => 1
366.87/291.59	   0 => 0
366.87/291.59	   false => 0
366.87/291.59	   const => 0
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(10)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 }-> cond(odd(x'), 1 + x') :|: z' = 1 + (1 + x'), z = 1, x' >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 }-> odd(x) :|: x >= 0, z = 1 + (1 + x)
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(11) SimplificationProof (BOTH BOUNDS(ID, ID))
366.87/291.59	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(12)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 }-> cond(odd(z' - 2), 1 + (z' - 2)) :|: z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 }-> odd(z - 2) :|: z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(13) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
366.87/291.59	Found the following analysis order by SCC decomposition:
366.87/291.59	
366.87/291.59	   { odd }
366.87/291.59	   { p }
366.87/291.59	   { cond }
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(14)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 }-> cond(odd(z' - 2), 1 + (z' - 2)) :|: z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 }-> odd(z - 2) :|: z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {odd}, {p}, {cond}
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(15) ResultPropagationProof (UPPER BOUND(ID))
366.87/291.59	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(16)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 }-> cond(odd(z' - 2), 1 + (z' - 2)) :|: z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 }-> odd(z - 2) :|: z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {odd}, {p}, {cond}
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(17) IntTrsBoundProof (UPPER BOUND(ID))
366.87/291.59	
366.87/291.59	Computed SIZE bound using CoFloCo for: odd
366.87/291.59	after applying outer abstraction to obtain an ITS,
366.87/291.59	resulting in: O(1) with polynomial bound: 1
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(18)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 }-> cond(odd(z' - 2), 1 + (z' - 2)) :|: z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 }-> odd(z - 2) :|: z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {odd}, {p}, {cond}
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: ?, size: O(1) [1]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(19) IntTrsBoundProof (UPPER BOUND(ID))
366.87/291.59	
366.87/291.59	Computed RUNTIME bound using CoFloCo for: odd
366.87/291.59	after applying outer abstraction to obtain an ITS,
366.87/291.59	resulting in: O(n^1) with polynomial bound: 2 + z
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(20)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 }-> cond(odd(z' - 2), 1 + (z' - 2)) :|: z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 }-> odd(z - 2) :|: z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {p}, {cond}
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: O(n^1) [2 + z], size: O(1) [1]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(21) ResultPropagationProof (UPPER BOUND(ID))
366.87/291.59	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(22)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 + z' }-> cond(s, 1 + (z' - 2)) :|: s >= 0, s <= 1, z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 + z }-> s' :|: s' >= 0, s' <= 1, z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {p}, {cond}
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: O(n^1) [2 + z], size: O(1) [1]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(23) IntTrsBoundProof (UPPER BOUND(ID))
366.87/291.59	
366.87/291.59	Computed SIZE bound using KoAT for: p
366.87/291.59	after applying outer abstraction to obtain an ITS,
366.87/291.59	resulting in: O(n^1) with polynomial bound: z
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(24)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 + z' }-> cond(s, 1 + (z' - 2)) :|: s >= 0, s <= 1, z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 + z }-> s' :|: s' >= 0, s' <= 1, z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {p}, {cond}
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: O(n^1) [2 + z], size: O(1) [1]
366.87/291.59	  p: runtime: ?, size: O(n^1) [z]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(25) IntTrsBoundProof (UPPER BOUND(ID))
366.87/291.59	
366.87/291.59	Computed RUNTIME bound using CoFloCo for: p
366.87/291.59	after applying outer abstraction to obtain an ITS,
366.87/291.59	resulting in: O(1) with polynomial bound: 1
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(26)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 + z' }-> cond(s, 1 + (z' - 2)) :|: s >= 0, s <= 1, z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 + z }-> s' :|: s' >= 0, s' <= 1, z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {cond}
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: O(n^1) [2 + z], size: O(1) [1]
366.87/291.59	  p: runtime: O(1) [1], size: O(n^1) [z]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(27) ResultPropagationProof (UPPER BOUND(ID))
366.87/291.59	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(28)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 + z' }-> cond(s, 1 + (z' - 2)) :|: s >= 0, s <= 1, z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 + z }-> s' :|: s' >= 0, s' <= 1, z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {cond}
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: O(n^1) [2 + z], size: O(1) [1]
366.87/291.59	  p: runtime: O(1) [1], size: O(n^1) [z]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(29) IntTrsBoundProof (UPPER BOUND(ID))
366.87/291.59	
366.87/291.59	Computed SIZE bound using CoFloCo for: cond
366.87/291.59	after applying outer abstraction to obtain an ITS,
366.87/291.59	resulting in: O(1) with polynomial bound: 0
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(30)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 + z' }-> cond(s, 1 + (z' - 2)) :|: s >= 0, s <= 1, z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 + z }-> s' :|: s' >= 0, s' <= 1, z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: {cond}
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: O(n^1) [2 + z], size: O(1) [1]
366.87/291.59	  p: runtime: O(1) [1], size: O(n^1) [z]
366.87/291.59	  cond: runtime: ?, size: O(1) [0]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(31) IntTrsBoundProof (UPPER BOUND(ID))
366.87/291.59	
366.87/291.59	Computed RUNTIME bound using CoFloCo for: cond
366.87/291.59	after applying outer abstraction to obtain an ITS,
366.87/291.59	resulting in: O(n^2) with polynomial bound: 9 + 4*z' + z'^2
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(32)
366.87/291.59	Obligation:
366.87/291.59	Complexity RNTS consisting of the following rules:
366.87/291.59	
366.87/291.59	   cond(z, z') -{ 3 + z' }-> cond(s, 1 + (z' - 2)) :|: s >= 0, s <= 1, z = 1, z' - 2 >= 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(1, 0) :|: z = 1, z' = 1 + 0
366.87/291.59	   cond(z, z') -{ 3 }-> cond(0, 0) :|: z = 1, z' = 0
366.87/291.59	   odd(z) -{ 1 + z }-> s' :|: s' >= 0, s' <= 1, z - 2 >= 0
366.87/291.59	   odd(z) -{ 1 }-> 1 :|: z = 1 + 0
366.87/291.59	   odd(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> 0 :|: z = 0
366.87/291.59	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
366.87/291.59	
366.87/291.59	Function symbols to be analyzed: 
366.87/291.59	Previous analysis results are:
366.87/291.59	  odd: runtime: O(n^1) [2 + z], size: O(1) [1]
366.87/291.59	  p: runtime: O(1) [1], size: O(n^1) [z]
366.87/291.59	  cond: runtime: O(n^2) [9 + 4*z' + z'^2], size: O(1) [0]
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(33) FinalProof (FINISHED)
366.87/291.59	Computed overall runtime complexity
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(34)
366.87/291.59	BOUNDS(1, n^2)
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(35) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
366.87/291.59	Transformed a relative TRS into a decreasing-loop problem.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(36)
366.87/291.59	Obligation:
366.87/291.59	Analyzing the following TRS for decreasing loops:
366.87/291.59	
366.87/291.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
366.87/291.59	
366.87/291.59	
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, x) -> cond(odd(x), p(x))
366.87/291.59	   odd(0) -> false
366.87/291.59	   odd(s(0)) -> true
366.87/291.59	   odd(s(s(x))) -> odd(x)
366.87/291.59	   p(0) -> 0
366.87/291.59	   p(s(x)) -> x
366.87/291.59	
366.87/291.59	S is empty.
366.87/291.59	Rewrite Strategy: INNERMOST
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(37) DecreasingLoopProof (LOWER BOUND(ID))
366.87/291.59	The following loop(s) give(s) rise to the lower bound Omega(n^1):
366.87/291.59	
366.87/291.59	The rewrite sequence
366.87/291.59	
366.87/291.59	odd(s(s(x))) ->^+ odd(x)
366.87/291.59	
366.87/291.59	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
366.87/291.59	
366.87/291.59	The pumping substitution is [x / s(s(x))].
366.87/291.59	
366.87/291.59	The result substitution is [ ].
366.87/291.59	
366.87/291.59	
366.87/291.59	
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(38)
366.87/291.59	Complex Obligation (BEST)
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(39)
366.87/291.59	Obligation:
366.87/291.59	Proved the lower bound n^1 for the following obligation:
366.87/291.59	
366.87/291.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
366.87/291.59	
366.87/291.59	
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, x) -> cond(odd(x), p(x))
366.87/291.59	   odd(0) -> false
366.87/291.59	   odd(s(0)) -> true
366.87/291.59	   odd(s(s(x))) -> odd(x)
366.87/291.59	   p(0) -> 0
366.87/291.59	   p(s(x)) -> x
366.87/291.59	
366.87/291.59	S is empty.
366.87/291.59	Rewrite Strategy: INNERMOST
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(40) LowerBoundPropagationProof (FINISHED)
366.87/291.59	Propagated lower bound.
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(41)
366.87/291.59	BOUNDS(n^1, INF)
366.87/291.59	
366.87/291.59	----------------------------------------
366.87/291.59	
366.87/291.59	(42)
366.87/291.59	Obligation:
366.87/291.59	Analyzing the following TRS for decreasing loops:
366.87/291.59	
366.87/291.59	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
366.87/291.59	
366.87/291.59	
366.87/291.59	The TRS R consists of the following rules:
366.87/291.59	
366.87/291.59	   cond(true, x) -> cond(odd(x), p(x))
366.87/291.59	   odd(0) -> false
366.87/291.59	   odd(s(0)) -> true
366.87/291.59	   odd(s(s(x))) -> odd(x)
366.87/291.59	   p(0) -> 0
366.87/291.59	   p(s(x)) -> x
366.87/291.60	
366.87/291.60	S is empty.
366.87/291.60	Rewrite Strategy: INNERMOST
366.96/291.64	EOF