/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 155 ms]
(4) CpxRelTRS
(5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
    (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CpxWeightedTrs
    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxTypedWeightedTrs
    (11) CompletionProof [UPPER BOUND(ID), 0 ms]
    (12) CpxTypedWeightedCompleteTrs
    (13) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CpxTypedWeightedCompleteTrs
    (15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (16) CpxRNTS
    (17) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) CpxRNTS
    (19) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
    (20) CpxRNTS
    (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (22) CpxRNTS
    (23) IntTrsBoundProof [UPPER BOUND(ID), 132 ms]
    (24) CpxRNTS
    (25) IntTrsBoundProof [UPPER BOUND(ID), 3 ms]
    (26) CpxRNTS
    (27) ResultPropagationProof [UPPER BOUND(ID), 1 ms]
    (28) CpxRNTS
    (29) IntTrsBoundProof [UPPER BOUND(ID), 530 ms]
    (30) CpxRNTS
    (31) IntTrsBoundProof [UPPER BOUND(ID), 156 ms]
    (32) CpxRNTS
    (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (34) CpxRNTS
    (35) IntTrsBoundProof [UPPER BOUND(ID), 1997 ms]
    (36) CpxRNTS
    (37) IntTrsBoundProof [UPPER BOUND(ID), 1576 ms]
    (38) CpxRNTS
    (39) ResultPropagationProof [UPPER BOUND(ID), 8 ms]
    (40) CpxRNTS
    (41) IntTrsBoundProof [UPPER BOUND(ID), 1618 ms]
    (42) CpxRNTS
    (43) IntTrsBoundProof [UPPER BOUND(ID), 1098 ms]
    (44) CpxRNTS
    (45) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (46) CpxRNTS
    (47) IntTrsBoundProof [UPPER BOUND(ID), 137 ms]
    (48) CpxRNTS
    (49) IntTrsBoundProof [UPPER BOUND(ID), 2 ms]
    (50) CpxRNTS
    (51) FinalProof [FINISHED, 0 ms]
    (52) BOUNDS(1, n^2)
(53) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(54) TRS for Loop Detection
    (55) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (56) BEST
        (57) proven lower bound
            (58) LowerBoundPropagationProof [FINISHED, 0 ms]
            (59) BOUNDS(n^1, INF)
        (60) TRS for Loop Detection


----------------------------------------

(0)
Obligation:
The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y))
   average(x, s(s(s(y)))) -> s(average(s(x), y))
   average(0, 0) -> 0
   average(0, s(0)) -> 0
   average(0, s(s(0))) -> s(0)

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0


----------------------------------------

(2)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y))
   average(x, s(s(s(y)))) -> s(average(s(x), y))
   average(0, 0) -> 0
   average(0, s(0)) -> 0
   average(0, s(s(0))) -> s(0)

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

Rewrite Strategy: FULL
----------------------------------------

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

(4)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y))
   average(x, s(s(s(y)))) -> s(average(s(x), y))
   average(0, 0) -> 0
   average(0, s(0)) -> 0
   average(0, s(s(0))) -> s(0)

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

Rewrite Strategy: FULL
----------------------------------------

(5) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

As the TRS is a non-duplicating overlay system, we have rc = irc.
----------------------------------------

(6)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y))
   average(x, s(s(s(y)))) -> s(average(s(x), y))
   average(0, 0) -> 0
   average(0, s(0)) -> 0
   average(0, s(s(0))) -> s(0)

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

Rewrite Strategy: INNERMOST
----------------------------------------

(7) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

(8)
Obligation:
The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y)) [1]
   average(x, s(s(s(y)))) -> s(average(s(x), y)) [1]
   average(0, 0) -> 0 [1]
   average(0, s(0)) -> 0 [1]
   average(0, s(s(0))) -> s(0) [1]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]

Rewrite Strategy: INNERMOST
----------------------------------------

(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(10)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y)) [1]
   average(x, s(s(s(y)))) -> s(average(s(x), y)) [1]
   average(0, 0) -> 0 [1]
   average(0, s(0)) -> 0 [1]
   average(0, s(s(0))) -> s(0) [1]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]

The TRS has the following type information:
average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
s :: s:0:cons_average -> s:0:cons_average
0 :: s:0:cons_average
encArg :: s:0:cons_average -> s:0:cons_average
cons_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_s :: s:0:cons_average -> s:0:cons_average
encode_0 :: s:0:cons_average

Rewrite Strategy: INNERMOST
----------------------------------------

(11) CompletionProof (UPPER BOUND(ID))
The transformation into a RNTS is sound, since:

(a) The obligation is a constructor system where every type has a constant constructor,

(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
none

(c) The following functions are completely defined:

   average_2
   encArg_1
   encode_average_2
   encode_s_1
   encode_0

Due to the following rules being added:

   encArg(v0) -> 0 [0]
   encode_average(v0, v1) -> 0 [0]
   encode_s(v0) -> 0 [0]
   encode_0 -> 0 [0]
   average(v0, v1) -> 0 [0]

And the following fresh constants: none

----------------------------------------

(12)
Obligation:
Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y)) [1]
   average(x, s(s(s(y)))) -> s(average(s(x), y)) [1]
   average(0, 0) -> 0 [1]
   average(0, s(0)) -> 0 [1]
   average(0, s(s(0))) -> s(0) [1]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2)) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encArg(v0) -> 0 [0]
   encode_average(v0, v1) -> 0 [0]
   encode_s(v0) -> 0 [0]
   encode_0 -> 0 [0]
   average(v0, v1) -> 0 [0]

The TRS has the following type information:
average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
s :: s:0:cons_average -> s:0:cons_average
0 :: s:0:cons_average
encArg :: s:0:cons_average -> s:0:cons_average
cons_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_s :: s:0:cons_average -> s:0:cons_average
encode_0 :: s:0:cons_average

Rewrite Strategy: INNERMOST
----------------------------------------

(13) NarrowingProof (BOTH BOUNDS(ID, ID))
Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
----------------------------------------

(14)
Obligation:
Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y)) [1]
   average(x, s(s(s(y)))) -> s(average(s(x), y)) [1]
   average(0, 0) -> 0 [1]
   average(0, s(0)) -> 0 [1]
   average(0, s(s(0))) -> s(0) [1]
   encArg(s(x_1)) -> s(encArg(x_1)) [0]
   encArg(0) -> 0 [0]
   encArg(cons_average(s(x_1'), s(x_11))) -> average(s(encArg(x_1')), s(encArg(x_11))) [0]
   encArg(cons_average(s(x_1'), 0)) -> average(s(encArg(x_1')), 0) [0]
   encArg(cons_average(s(x_1'), cons_average(x_12, x_2''))) -> average(s(encArg(x_1')), average(encArg(x_12), encArg(x_2''))) [0]
   encArg(cons_average(s(x_1'), x_2)) -> average(s(encArg(x_1')), 0) [0]
   encArg(cons_average(0, s(x_13))) -> average(0, s(encArg(x_13))) [0]
   encArg(cons_average(0, 0)) -> average(0, 0) [0]
   encArg(cons_average(0, cons_average(x_14, x_21))) -> average(0, average(encArg(x_14), encArg(x_21))) [0]
   encArg(cons_average(0, x_2)) -> average(0, 0) [0]
   encArg(cons_average(cons_average(x_1'', x_2'), s(x_15))) -> average(average(encArg(x_1''), encArg(x_2')), s(encArg(x_15))) [0]
   encArg(cons_average(cons_average(x_1'', x_2'), 0)) -> average(average(encArg(x_1''), encArg(x_2')), 0) [0]
   encArg(cons_average(cons_average(x_1'', x_2'), cons_average(x_16, x_22))) -> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) [0]
   encArg(cons_average(cons_average(x_1'', x_2'), x_2)) -> average(average(encArg(x_1''), encArg(x_2')), 0) [0]
   encArg(cons_average(x_1, s(x_17))) -> average(0, s(encArg(x_17))) [0]
   encArg(cons_average(x_1, 0)) -> average(0, 0) [0]
   encArg(cons_average(x_1, cons_average(x_18, x_23))) -> average(0, average(encArg(x_18), encArg(x_23))) [0]
   encArg(cons_average(x_1, x_2)) -> average(0, 0) [0]
   encode_average(s(x_19), s(x_111)) -> average(s(encArg(x_19)), s(encArg(x_111))) [0]
   encode_average(s(x_19), 0) -> average(s(encArg(x_19)), 0) [0]
   encode_average(s(x_19), cons_average(x_112, x_25)) -> average(s(encArg(x_19)), average(encArg(x_112), encArg(x_25))) [0]
   encode_average(s(x_19), x_2) -> average(s(encArg(x_19)), 0) [0]
   encode_average(0, s(x_113)) -> average(0, s(encArg(x_113))) [0]
   encode_average(0, 0) -> average(0, 0) [0]
   encode_average(0, cons_average(x_114, x_26)) -> average(0, average(encArg(x_114), encArg(x_26))) [0]
   encode_average(0, x_2) -> average(0, 0) [0]
   encode_average(cons_average(x_110, x_24), s(x_115)) -> average(average(encArg(x_110), encArg(x_24)), s(encArg(x_115))) [0]
   encode_average(cons_average(x_110, x_24), 0) -> average(average(encArg(x_110), encArg(x_24)), 0) [0]
   encode_average(cons_average(x_110, x_24), cons_average(x_116, x_27)) -> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) [0]
   encode_average(cons_average(x_110, x_24), x_2) -> average(average(encArg(x_110), encArg(x_24)), 0) [0]
   encode_average(x_1, s(x_117)) -> average(0, s(encArg(x_117))) [0]
   encode_average(x_1, 0) -> average(0, 0) [0]
   encode_average(x_1, cons_average(x_118, x_28)) -> average(0, average(encArg(x_118), encArg(x_28))) [0]
   encode_average(x_1, x_2) -> average(0, 0) [0]
   encode_s(x_1) -> s(encArg(x_1)) [0]
   encode_0 -> 0 [0]
   encArg(v0) -> 0 [0]
   encode_average(v0, v1) -> 0 [0]
   encode_s(v0) -> 0 [0]
   encode_0 -> 0 [0]
   average(v0, v1) -> 0 [0]

The TRS has the following type information:
average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
s :: s:0:cons_average -> s:0:cons_average
0 :: s:0:cons_average
encArg :: s:0:cons_average -> s:0:cons_average
cons_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_average :: s:0:cons_average -> s:0:cons_average -> s:0:cons_average
encode_s :: s:0:cons_average -> s:0:cons_average
encode_0 :: s:0:cons_average

Rewrite Strategy: INNERMOST
----------------------------------------

(15) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   0 => 0

----------------------------------------

(16)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(x, 1 + y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   average(z, z') -{ 1 }-> 1 + average(1 + x, y) :|: x >= 0, y >= 0, z' = 1 + (1 + (1 + y)), z = x
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + x_1 + 0, x_1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_13)) :|: z = 1 + 0 + (1 + x_13), x_13 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: z = 1 + (1 + x_1') + 0, x_1' >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_2 >= 0, z' = x_2, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(x_115)) :|: x_115 >= 0, z' = 1 + x_115, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: x_1 >= 0, z = x_1, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: x_2 >= 0, z' = x_2, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = x_1, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(x_113)) :|: x_113 >= 0, z = 0, z' = 1 + x_113
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(x_117)) :|: x_1 >= 0, x_117 >= 0, z' = 1 + x_117, z = x_1
   encode_average(z, z') -{ 0 }-> average(1 + encArg(x_19), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z = 1 + x_19, x_19 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(x_19), 0) :|: z = 1 + x_19, z' = 0, x_19 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(x_19), 0) :|: x_2 >= 0, z' = x_2, z = 1 + x_19, x_19 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(x_19), 1 + encArg(x_111)) :|: z' = 1 + x_111, z = 1 + x_19, x_19 >= 0, x_111 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1


----------------------------------------

(17) SimplificationProof (BOTH BOUNDS(ID, ID))
Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
----------------------------------------

(18)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0


----------------------------------------

(19) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
Found the following analysis order by SCC decomposition:

   { encode_0 }
   { average }
   { encArg }
   { encode_average }
   { encode_s }

----------------------------------------

(20)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {encode_0}, {average}, {encArg}, {encode_average}, {encode_s}

----------------------------------------

(21) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(22)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {encode_0}, {average}, {encArg}, {encode_average}, {encode_s}

----------------------------------------

(23) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encode_0
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(24)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {encode_0}, {average}, {encArg}, {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: ?, size: O(1) [0]

----------------------------------------

(25) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: encode_0
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(26)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {average}, {encArg}, {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]

----------------------------------------

(27) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(28)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {average}, {encArg}, {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]

----------------------------------------

(29) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using KoAT for: average
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: z + z'

----------------------------------------

(30)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {average}, {encArg}, {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: ?, size: O(n^1) [z + z']

----------------------------------------

(31) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: average
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 3 + 2*z + z'

----------------------------------------

(32)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 1 }-> average(z - 1, 1 + z') :|: z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 1 }-> 1 + average(1 + z, z' - 3) :|: z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z = 1 + 0 + 0
   encArg(z) -{ 0 }-> average(0, 0) :|: z - 1 >= 0
   encArg(z) -{ 0 }-> average(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z = 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z' >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(0, 0) :|: z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {encArg}, {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']

----------------------------------------

(33) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(34)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {encArg}, {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']

----------------------------------------

(35) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encArg
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 6*z

----------------------------------------

(36)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {encArg}, {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: ?, size: O(n^1) [6*z]

----------------------------------------

(37) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: encArg
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 3 + 437*z + 144*z^2

----------------------------------------

(38)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), average(encArg(x_16), encArg(x_22))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 0 }-> average(average(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_14), encArg(x_21))) :|: x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 0 }-> average(0, average(encArg(x_18), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> average(0, 1 + encArg(x_17)) :|: x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 0 }-> average(0, 1 + encArg(z - 2)) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), average(encArg(x_12), encArg(x_2''))) :|: z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 0 }-> average(1 + encArg(x_1'), 1 + encArg(x_11)) :|: x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ 0 }-> average(1 + encArg(z - 2), 0) :|: z - 2 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), average(encArg(x_116), encArg(x_27))) :|: x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 0) :|: z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(average(encArg(x_110), encArg(x_24)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_114), encArg(x_26))) :|: x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ 0 }-> average(0, average(encArg(x_118), encArg(x_28))) :|: z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 0 }-> average(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), average(encArg(x_112), encArg(x_25))) :|: x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 0) :|: z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ 0 }-> average(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0

Function symbols to be analyzed: {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [6*z]

----------------------------------------

(39) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(40)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 12 + 2*s8 + s9 + 437*x_1' + 144*x_1'^2 + 437*x_11 + 144*x_11^2 }-> s10 :|: s8 >= 0, s8 <= 6 * x_1', s9 >= 0, s9 <= 6 * x_11, s10 >= 0, s10 <= 1 + s8 + (1 + s9), x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ -290 + 2*s11 + -139*z + 144*z^2 }-> s12 :|: s11 >= 0, s11 <= 6 * (z - 2), s12 >= 0, s12 <= 1 + s11 + 0, z - 2 >= 0
   encArg(z) -{ 17 + 2*s13 + 2*s14 + s15 + s16 + 437*x_1' + 144*x_1'^2 + 437*x_12 + 144*x_12^2 + 437*x_2'' + 144*x_2''^2 }-> s17 :|: s13 >= 0, s13 <= 6 * x_1', s14 >= 0, s14 <= 6 * x_12, s15 >= 0, s15 <= 6 * x_2'', s16 >= 0, s16 <= s14 + s15, s17 >= 0, s17 <= 1 + s13 + s16, z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 8 + 2*s18 + 437*x_1' + 144*x_1'^2 }-> s19 :|: s18 >= 0, s18 <= 6 * x_1', s19 >= 0, s19 <= 1 + s18 + 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ -291 + s20 + -139*z + 144*z^2 }-> s21 :|: s20 >= 0, s20 <= 6 * (z - 2), s21 >= 0, s21 <= 0 + (1 + s20), z - 2 >= 0
   encArg(z) -{ 12 + 2*s22 + s23 + s24 + 437*x_14 + 144*x_14^2 + 437*x_21 + 144*x_21^2 }-> s25 :|: s22 >= 0, s22 <= 6 * x_14, s23 >= 0, s23 <= 6 * x_21, s24 >= 0, s24 <= s22 + s23, s25 >= 0, s25 <= 0 + s24, x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 16 + 2*s26 + s27 + 2*s28 + s29 + 437*x_1'' + 144*x_1''^2 + 437*x_15 + 144*x_15^2 + 437*x_2' + 144*x_2'^2 }-> s30 :|: s26 >= 0, s26 <= 6 * x_1'', s27 >= 0, s27 <= 6 * x_2', s28 >= 0, s28 <= s26 + s27, s29 >= 0, s29 <= 6 * x_15, s30 >= 0, s30 <= s28 + (1 + s29), x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 12 + 2*s31 + s32 + 2*s33 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s34 :|: s31 >= 0, s31 <= 6 * x_1'', s32 >= 0, s32 <= 6 * x_2', s33 >= 0, s33 <= s31 + s32, s34 >= 0, s34 <= s33 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 21 + 2*s35 + s36 + 2*s37 + 2*s38 + s39 + s40 + 437*x_1'' + 144*x_1''^2 + 437*x_16 + 144*x_16^2 + 437*x_2' + 144*x_2'^2 + 437*x_22 + 144*x_22^2 }-> s41 :|: s35 >= 0, s35 <= 6 * x_1'', s36 >= 0, s36 <= 6 * x_2', s37 >= 0, s37 <= s35 + s36, s38 >= 0, s38 <= 6 * x_16, s39 >= 0, s39 <= 6 * x_22, s40 >= 0, s40 <= s38 + s39, s41 >= 0, s41 <= s37 + s40, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 12 + 2*s42 + s43 + 2*s44 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s45 :|: s42 >= 0, s42 <= 6 * x_1'', s43 >= 0, s43 <= 6 * x_2', s44 >= 0, s44 <= s42 + s43, s45 >= 0, s45 <= s44 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 7 + s46 + 437*x_17 + 144*x_17^2 }-> s47 :|: s46 >= 0, s46 <= 6 * x_17, s47 >= 0, s47 <= 0 + (1 + s46), x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 12 + 2*s48 + s49 + s50 + 437*x_18 + 144*x_18^2 + 437*x_23 + 144*x_23^2 }-> s51 :|: s48 >= 0, s48 <= 6 * x_18, s49 >= 0, s49 <= 6 * x_23, s50 >= 0, s50 <= s48 + s49, s51 >= 0, s51 <= 0 + s50, x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -290 + 149*z + 144*z^2 }-> 1 + s7 :|: s7 >= 0, s7 <= 6 * (z - 1), z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ -574 + 2*s52 + s53 + 149*z + 144*z^2 + 149*z' + 144*z'^2 }-> s54 :|: s52 >= 0, s52 <= 6 * (z - 1), s53 >= 0, s53 <= 6 * (z' - 1), s54 >= 0, s54 <= 1 + s52 + (1 + s53), z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s55 + 149*z + 144*z^2 }-> s56 :|: s55 >= 0, s55 <= 6 * (z - 1), s56 >= 0, s56 <= 1 + s55 + 0, z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ -276 + 2*s57 + 2*s58 + s59 + s60 + 437*x_112 + 144*x_112^2 + 437*x_25 + 144*x_25^2 + 149*z + 144*z^2 }-> s61 :|: s57 >= 0, s57 <= 6 * (z - 1), s58 >= 0, s58 <= 6 * x_112, s59 >= 0, s59 <= 6 * x_25, s60 >= 0, s60 <= s58 + s59, s61 >= 0, s61 <= 1 + s57 + s60, x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s62 + 149*z + 144*z^2 }-> s63 :|: s62 >= 0, s62 <= 6 * (z - 1), s63 >= 0, s63 <= 1 + s62 + 0, z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ -286 + s64 + 149*z' + 144*z'^2 }-> s65 :|: s64 >= 0, s64 <= 6 * (z' - 1), s65 >= 0, s65 <= 0 + (1 + s64), z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 12 + 2*s66 + s67 + s68 + 437*x_114 + 144*x_114^2 + 437*x_26 + 144*x_26^2 }-> s69 :|: s66 >= 0, s66 <= 6 * x_114, s67 >= 0, s67 <= 6 * x_26, s68 >= 0, s68 <= s66 + s67, s69 >= 0, s69 <= 0 + s68, x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ -277 + 2*s70 + s71 + 2*s72 + s73 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 + 149*z' + 144*z'^2 }-> s74 :|: s70 >= 0, s70 <= 6 * x_110, s71 >= 0, s71 <= 6 * x_24, s72 >= 0, s72 <= s70 + s71, s73 >= 0, s73 <= 6 * (z' - 1), s74 >= 0, s74 <= s72 + (1 + s73), z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s75 + s76 + 2*s77 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s78 :|: s75 >= 0, s75 <= 6 * x_110, s76 >= 0, s76 <= 6 * x_24, s77 >= 0, s77 <= s75 + s76, s78 >= 0, s78 <= s77 + 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 21 + 2*s79 + s80 + 2*s81 + 2*s82 + s83 + s84 + 437*x_110 + 144*x_110^2 + 437*x_116 + 144*x_116^2 + 437*x_24 + 144*x_24^2 + 437*x_27 + 144*x_27^2 }-> s85 :|: s79 >= 0, s79 <= 6 * x_110, s80 >= 0, s80 <= 6 * x_24, s81 >= 0, s81 <= s79 + s80, s82 >= 0, s82 <= 6 * x_116, s83 >= 0, s83 <= 6 * x_27, s84 >= 0, s84 <= s82 + s83, s85 >= 0, s85 <= s81 + s84, x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s86 + s87 + 2*s88 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s89 :|: s86 >= 0, s86 <= 6 * x_110, s87 >= 0, s87 <= 6 * x_24, s88 >= 0, s88 <= s86 + s87, s89 >= 0, s89 <= s88 + 0, z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ -286 + s90 + 149*z' + 144*z'^2 }-> s91 :|: s90 >= 0, s90 <= 6 * (z' - 1), s91 >= 0, s91 <= 0 + (1 + s90), z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 12 + 2*s92 + s93 + s94 + 437*x_118 + 144*x_118^2 + 437*x_28 + 144*x_28^2 }-> s95 :|: s92 >= 0, s92 <= 6 * x_118, s93 >= 0, s93 <= 6 * x_28, s94 >= 0, s94 <= s92 + s93, s95 >= 0, s95 <= 0 + s94, z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 3 + 437*z + 144*z^2 }-> 1 + s96 :|: s96 >= 0, s96 <= 6 * z, z >= 0

Function symbols to be analyzed: {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [6*z]

----------------------------------------

(41) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using KoAT for: encode_average
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 6*z + 6*z'

----------------------------------------

(42)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 12 + 2*s8 + s9 + 437*x_1' + 144*x_1'^2 + 437*x_11 + 144*x_11^2 }-> s10 :|: s8 >= 0, s8 <= 6 * x_1', s9 >= 0, s9 <= 6 * x_11, s10 >= 0, s10 <= 1 + s8 + (1 + s9), x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ -290 + 2*s11 + -139*z + 144*z^2 }-> s12 :|: s11 >= 0, s11 <= 6 * (z - 2), s12 >= 0, s12 <= 1 + s11 + 0, z - 2 >= 0
   encArg(z) -{ 17 + 2*s13 + 2*s14 + s15 + s16 + 437*x_1' + 144*x_1'^2 + 437*x_12 + 144*x_12^2 + 437*x_2'' + 144*x_2''^2 }-> s17 :|: s13 >= 0, s13 <= 6 * x_1', s14 >= 0, s14 <= 6 * x_12, s15 >= 0, s15 <= 6 * x_2'', s16 >= 0, s16 <= s14 + s15, s17 >= 0, s17 <= 1 + s13 + s16, z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 8 + 2*s18 + 437*x_1' + 144*x_1'^2 }-> s19 :|: s18 >= 0, s18 <= 6 * x_1', s19 >= 0, s19 <= 1 + s18 + 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ -291 + s20 + -139*z + 144*z^2 }-> s21 :|: s20 >= 0, s20 <= 6 * (z - 2), s21 >= 0, s21 <= 0 + (1 + s20), z - 2 >= 0
   encArg(z) -{ 12 + 2*s22 + s23 + s24 + 437*x_14 + 144*x_14^2 + 437*x_21 + 144*x_21^2 }-> s25 :|: s22 >= 0, s22 <= 6 * x_14, s23 >= 0, s23 <= 6 * x_21, s24 >= 0, s24 <= s22 + s23, s25 >= 0, s25 <= 0 + s24, x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 16 + 2*s26 + s27 + 2*s28 + s29 + 437*x_1'' + 144*x_1''^2 + 437*x_15 + 144*x_15^2 + 437*x_2' + 144*x_2'^2 }-> s30 :|: s26 >= 0, s26 <= 6 * x_1'', s27 >= 0, s27 <= 6 * x_2', s28 >= 0, s28 <= s26 + s27, s29 >= 0, s29 <= 6 * x_15, s30 >= 0, s30 <= s28 + (1 + s29), x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 12 + 2*s31 + s32 + 2*s33 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s34 :|: s31 >= 0, s31 <= 6 * x_1'', s32 >= 0, s32 <= 6 * x_2', s33 >= 0, s33 <= s31 + s32, s34 >= 0, s34 <= s33 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 21 + 2*s35 + s36 + 2*s37 + 2*s38 + s39 + s40 + 437*x_1'' + 144*x_1''^2 + 437*x_16 + 144*x_16^2 + 437*x_2' + 144*x_2'^2 + 437*x_22 + 144*x_22^2 }-> s41 :|: s35 >= 0, s35 <= 6 * x_1'', s36 >= 0, s36 <= 6 * x_2', s37 >= 0, s37 <= s35 + s36, s38 >= 0, s38 <= 6 * x_16, s39 >= 0, s39 <= 6 * x_22, s40 >= 0, s40 <= s38 + s39, s41 >= 0, s41 <= s37 + s40, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 12 + 2*s42 + s43 + 2*s44 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s45 :|: s42 >= 0, s42 <= 6 * x_1'', s43 >= 0, s43 <= 6 * x_2', s44 >= 0, s44 <= s42 + s43, s45 >= 0, s45 <= s44 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 7 + s46 + 437*x_17 + 144*x_17^2 }-> s47 :|: s46 >= 0, s46 <= 6 * x_17, s47 >= 0, s47 <= 0 + (1 + s46), x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 12 + 2*s48 + s49 + s50 + 437*x_18 + 144*x_18^2 + 437*x_23 + 144*x_23^2 }-> s51 :|: s48 >= 0, s48 <= 6 * x_18, s49 >= 0, s49 <= 6 * x_23, s50 >= 0, s50 <= s48 + s49, s51 >= 0, s51 <= 0 + s50, x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -290 + 149*z + 144*z^2 }-> 1 + s7 :|: s7 >= 0, s7 <= 6 * (z - 1), z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ -574 + 2*s52 + s53 + 149*z + 144*z^2 + 149*z' + 144*z'^2 }-> s54 :|: s52 >= 0, s52 <= 6 * (z - 1), s53 >= 0, s53 <= 6 * (z' - 1), s54 >= 0, s54 <= 1 + s52 + (1 + s53), z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s55 + 149*z + 144*z^2 }-> s56 :|: s55 >= 0, s55 <= 6 * (z - 1), s56 >= 0, s56 <= 1 + s55 + 0, z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ -276 + 2*s57 + 2*s58 + s59 + s60 + 437*x_112 + 144*x_112^2 + 437*x_25 + 144*x_25^2 + 149*z + 144*z^2 }-> s61 :|: s57 >= 0, s57 <= 6 * (z - 1), s58 >= 0, s58 <= 6 * x_112, s59 >= 0, s59 <= 6 * x_25, s60 >= 0, s60 <= s58 + s59, s61 >= 0, s61 <= 1 + s57 + s60, x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s62 + 149*z + 144*z^2 }-> s63 :|: s62 >= 0, s62 <= 6 * (z - 1), s63 >= 0, s63 <= 1 + s62 + 0, z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ -286 + s64 + 149*z' + 144*z'^2 }-> s65 :|: s64 >= 0, s64 <= 6 * (z' - 1), s65 >= 0, s65 <= 0 + (1 + s64), z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 12 + 2*s66 + s67 + s68 + 437*x_114 + 144*x_114^2 + 437*x_26 + 144*x_26^2 }-> s69 :|: s66 >= 0, s66 <= 6 * x_114, s67 >= 0, s67 <= 6 * x_26, s68 >= 0, s68 <= s66 + s67, s69 >= 0, s69 <= 0 + s68, x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ -277 + 2*s70 + s71 + 2*s72 + s73 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 + 149*z' + 144*z'^2 }-> s74 :|: s70 >= 0, s70 <= 6 * x_110, s71 >= 0, s71 <= 6 * x_24, s72 >= 0, s72 <= s70 + s71, s73 >= 0, s73 <= 6 * (z' - 1), s74 >= 0, s74 <= s72 + (1 + s73), z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s75 + s76 + 2*s77 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s78 :|: s75 >= 0, s75 <= 6 * x_110, s76 >= 0, s76 <= 6 * x_24, s77 >= 0, s77 <= s75 + s76, s78 >= 0, s78 <= s77 + 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 21 + 2*s79 + s80 + 2*s81 + 2*s82 + s83 + s84 + 437*x_110 + 144*x_110^2 + 437*x_116 + 144*x_116^2 + 437*x_24 + 144*x_24^2 + 437*x_27 + 144*x_27^2 }-> s85 :|: s79 >= 0, s79 <= 6 * x_110, s80 >= 0, s80 <= 6 * x_24, s81 >= 0, s81 <= s79 + s80, s82 >= 0, s82 <= 6 * x_116, s83 >= 0, s83 <= 6 * x_27, s84 >= 0, s84 <= s82 + s83, s85 >= 0, s85 <= s81 + s84, x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s86 + s87 + 2*s88 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s89 :|: s86 >= 0, s86 <= 6 * x_110, s87 >= 0, s87 <= 6 * x_24, s88 >= 0, s88 <= s86 + s87, s89 >= 0, s89 <= s88 + 0, z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ -286 + s90 + 149*z' + 144*z'^2 }-> s91 :|: s90 >= 0, s90 <= 6 * (z' - 1), s91 >= 0, s91 <= 0 + (1 + s90), z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 12 + 2*s92 + s93 + s94 + 437*x_118 + 144*x_118^2 + 437*x_28 + 144*x_28^2 }-> s95 :|: s92 >= 0, s92 <= 6 * x_118, s93 >= 0, s93 <= 6 * x_28, s94 >= 0, s94 <= s92 + s93, s95 >= 0, s95 <= 0 + s94, z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 3 + 437*z + 144*z^2 }-> 1 + s96 :|: s96 >= 0, s96 <= 6 * z, z >= 0

Function symbols to be analyzed: {encode_average}, {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [6*z]
  encode_average: runtime: ?, size: O(n^1) [6*z + 6*z']

----------------------------------------

(43) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: encode_average
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 81 + 4296*z + 1728*z^2 + 4230*z' + 1728*z'^2

----------------------------------------

(44)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 12 + 2*s8 + s9 + 437*x_1' + 144*x_1'^2 + 437*x_11 + 144*x_11^2 }-> s10 :|: s8 >= 0, s8 <= 6 * x_1', s9 >= 0, s9 <= 6 * x_11, s10 >= 0, s10 <= 1 + s8 + (1 + s9), x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ -290 + 2*s11 + -139*z + 144*z^2 }-> s12 :|: s11 >= 0, s11 <= 6 * (z - 2), s12 >= 0, s12 <= 1 + s11 + 0, z - 2 >= 0
   encArg(z) -{ 17 + 2*s13 + 2*s14 + s15 + s16 + 437*x_1' + 144*x_1'^2 + 437*x_12 + 144*x_12^2 + 437*x_2'' + 144*x_2''^2 }-> s17 :|: s13 >= 0, s13 <= 6 * x_1', s14 >= 0, s14 <= 6 * x_12, s15 >= 0, s15 <= 6 * x_2'', s16 >= 0, s16 <= s14 + s15, s17 >= 0, s17 <= 1 + s13 + s16, z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 8 + 2*s18 + 437*x_1' + 144*x_1'^2 }-> s19 :|: s18 >= 0, s18 <= 6 * x_1', s19 >= 0, s19 <= 1 + s18 + 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ -291 + s20 + -139*z + 144*z^2 }-> s21 :|: s20 >= 0, s20 <= 6 * (z - 2), s21 >= 0, s21 <= 0 + (1 + s20), z - 2 >= 0
   encArg(z) -{ 12 + 2*s22 + s23 + s24 + 437*x_14 + 144*x_14^2 + 437*x_21 + 144*x_21^2 }-> s25 :|: s22 >= 0, s22 <= 6 * x_14, s23 >= 0, s23 <= 6 * x_21, s24 >= 0, s24 <= s22 + s23, s25 >= 0, s25 <= 0 + s24, x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 16 + 2*s26 + s27 + 2*s28 + s29 + 437*x_1'' + 144*x_1''^2 + 437*x_15 + 144*x_15^2 + 437*x_2' + 144*x_2'^2 }-> s30 :|: s26 >= 0, s26 <= 6 * x_1'', s27 >= 0, s27 <= 6 * x_2', s28 >= 0, s28 <= s26 + s27, s29 >= 0, s29 <= 6 * x_15, s30 >= 0, s30 <= s28 + (1 + s29), x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 12 + 2*s31 + s32 + 2*s33 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s34 :|: s31 >= 0, s31 <= 6 * x_1'', s32 >= 0, s32 <= 6 * x_2', s33 >= 0, s33 <= s31 + s32, s34 >= 0, s34 <= s33 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 21 + 2*s35 + s36 + 2*s37 + 2*s38 + s39 + s40 + 437*x_1'' + 144*x_1''^2 + 437*x_16 + 144*x_16^2 + 437*x_2' + 144*x_2'^2 + 437*x_22 + 144*x_22^2 }-> s41 :|: s35 >= 0, s35 <= 6 * x_1'', s36 >= 0, s36 <= 6 * x_2', s37 >= 0, s37 <= s35 + s36, s38 >= 0, s38 <= 6 * x_16, s39 >= 0, s39 <= 6 * x_22, s40 >= 0, s40 <= s38 + s39, s41 >= 0, s41 <= s37 + s40, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 12 + 2*s42 + s43 + 2*s44 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s45 :|: s42 >= 0, s42 <= 6 * x_1'', s43 >= 0, s43 <= 6 * x_2', s44 >= 0, s44 <= s42 + s43, s45 >= 0, s45 <= s44 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 7 + s46 + 437*x_17 + 144*x_17^2 }-> s47 :|: s46 >= 0, s46 <= 6 * x_17, s47 >= 0, s47 <= 0 + (1 + s46), x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 12 + 2*s48 + s49 + s50 + 437*x_18 + 144*x_18^2 + 437*x_23 + 144*x_23^2 }-> s51 :|: s48 >= 0, s48 <= 6 * x_18, s49 >= 0, s49 <= 6 * x_23, s50 >= 0, s50 <= s48 + s49, s51 >= 0, s51 <= 0 + s50, x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -290 + 149*z + 144*z^2 }-> 1 + s7 :|: s7 >= 0, s7 <= 6 * (z - 1), z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ -574 + 2*s52 + s53 + 149*z + 144*z^2 + 149*z' + 144*z'^2 }-> s54 :|: s52 >= 0, s52 <= 6 * (z - 1), s53 >= 0, s53 <= 6 * (z' - 1), s54 >= 0, s54 <= 1 + s52 + (1 + s53), z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s55 + 149*z + 144*z^2 }-> s56 :|: s55 >= 0, s55 <= 6 * (z - 1), s56 >= 0, s56 <= 1 + s55 + 0, z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ -276 + 2*s57 + 2*s58 + s59 + s60 + 437*x_112 + 144*x_112^2 + 437*x_25 + 144*x_25^2 + 149*z + 144*z^2 }-> s61 :|: s57 >= 0, s57 <= 6 * (z - 1), s58 >= 0, s58 <= 6 * x_112, s59 >= 0, s59 <= 6 * x_25, s60 >= 0, s60 <= s58 + s59, s61 >= 0, s61 <= 1 + s57 + s60, x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s62 + 149*z + 144*z^2 }-> s63 :|: s62 >= 0, s62 <= 6 * (z - 1), s63 >= 0, s63 <= 1 + s62 + 0, z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ -286 + s64 + 149*z' + 144*z'^2 }-> s65 :|: s64 >= 0, s64 <= 6 * (z' - 1), s65 >= 0, s65 <= 0 + (1 + s64), z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 12 + 2*s66 + s67 + s68 + 437*x_114 + 144*x_114^2 + 437*x_26 + 144*x_26^2 }-> s69 :|: s66 >= 0, s66 <= 6 * x_114, s67 >= 0, s67 <= 6 * x_26, s68 >= 0, s68 <= s66 + s67, s69 >= 0, s69 <= 0 + s68, x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ -277 + 2*s70 + s71 + 2*s72 + s73 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 + 149*z' + 144*z'^2 }-> s74 :|: s70 >= 0, s70 <= 6 * x_110, s71 >= 0, s71 <= 6 * x_24, s72 >= 0, s72 <= s70 + s71, s73 >= 0, s73 <= 6 * (z' - 1), s74 >= 0, s74 <= s72 + (1 + s73), z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s75 + s76 + 2*s77 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s78 :|: s75 >= 0, s75 <= 6 * x_110, s76 >= 0, s76 <= 6 * x_24, s77 >= 0, s77 <= s75 + s76, s78 >= 0, s78 <= s77 + 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 21 + 2*s79 + s80 + 2*s81 + 2*s82 + s83 + s84 + 437*x_110 + 144*x_110^2 + 437*x_116 + 144*x_116^2 + 437*x_24 + 144*x_24^2 + 437*x_27 + 144*x_27^2 }-> s85 :|: s79 >= 0, s79 <= 6 * x_110, s80 >= 0, s80 <= 6 * x_24, s81 >= 0, s81 <= s79 + s80, s82 >= 0, s82 <= 6 * x_116, s83 >= 0, s83 <= 6 * x_27, s84 >= 0, s84 <= s82 + s83, s85 >= 0, s85 <= s81 + s84, x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s86 + s87 + 2*s88 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s89 :|: s86 >= 0, s86 <= 6 * x_110, s87 >= 0, s87 <= 6 * x_24, s88 >= 0, s88 <= s86 + s87, s89 >= 0, s89 <= s88 + 0, z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ -286 + s90 + 149*z' + 144*z'^2 }-> s91 :|: s90 >= 0, s90 <= 6 * (z' - 1), s91 >= 0, s91 <= 0 + (1 + s90), z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 12 + 2*s92 + s93 + s94 + 437*x_118 + 144*x_118^2 + 437*x_28 + 144*x_28^2 }-> s95 :|: s92 >= 0, s92 <= 6 * x_118, s93 >= 0, s93 <= 6 * x_28, s94 >= 0, s94 <= s92 + s93, s95 >= 0, s95 <= 0 + s94, z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 3 + 437*z + 144*z^2 }-> 1 + s96 :|: s96 >= 0, s96 <= 6 * z, z >= 0

Function symbols to be analyzed: {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [6*z]
  encode_average: runtime: O(n^2) [81 + 4296*z + 1728*z^2 + 4230*z' + 1728*z'^2], size: O(n^1) [6*z + 6*z']

----------------------------------------

(45) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(46)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 12 + 2*s8 + s9 + 437*x_1' + 144*x_1'^2 + 437*x_11 + 144*x_11^2 }-> s10 :|: s8 >= 0, s8 <= 6 * x_1', s9 >= 0, s9 <= 6 * x_11, s10 >= 0, s10 <= 1 + s8 + (1 + s9), x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ -290 + 2*s11 + -139*z + 144*z^2 }-> s12 :|: s11 >= 0, s11 <= 6 * (z - 2), s12 >= 0, s12 <= 1 + s11 + 0, z - 2 >= 0
   encArg(z) -{ 17 + 2*s13 + 2*s14 + s15 + s16 + 437*x_1' + 144*x_1'^2 + 437*x_12 + 144*x_12^2 + 437*x_2'' + 144*x_2''^2 }-> s17 :|: s13 >= 0, s13 <= 6 * x_1', s14 >= 0, s14 <= 6 * x_12, s15 >= 0, s15 <= 6 * x_2'', s16 >= 0, s16 <= s14 + s15, s17 >= 0, s17 <= 1 + s13 + s16, z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 8 + 2*s18 + 437*x_1' + 144*x_1'^2 }-> s19 :|: s18 >= 0, s18 <= 6 * x_1', s19 >= 0, s19 <= 1 + s18 + 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ -291 + s20 + -139*z + 144*z^2 }-> s21 :|: s20 >= 0, s20 <= 6 * (z - 2), s21 >= 0, s21 <= 0 + (1 + s20), z - 2 >= 0
   encArg(z) -{ 12 + 2*s22 + s23 + s24 + 437*x_14 + 144*x_14^2 + 437*x_21 + 144*x_21^2 }-> s25 :|: s22 >= 0, s22 <= 6 * x_14, s23 >= 0, s23 <= 6 * x_21, s24 >= 0, s24 <= s22 + s23, s25 >= 0, s25 <= 0 + s24, x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 16 + 2*s26 + s27 + 2*s28 + s29 + 437*x_1'' + 144*x_1''^2 + 437*x_15 + 144*x_15^2 + 437*x_2' + 144*x_2'^2 }-> s30 :|: s26 >= 0, s26 <= 6 * x_1'', s27 >= 0, s27 <= 6 * x_2', s28 >= 0, s28 <= s26 + s27, s29 >= 0, s29 <= 6 * x_15, s30 >= 0, s30 <= s28 + (1 + s29), x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 12 + 2*s31 + s32 + 2*s33 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s34 :|: s31 >= 0, s31 <= 6 * x_1'', s32 >= 0, s32 <= 6 * x_2', s33 >= 0, s33 <= s31 + s32, s34 >= 0, s34 <= s33 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 21 + 2*s35 + s36 + 2*s37 + 2*s38 + s39 + s40 + 437*x_1'' + 144*x_1''^2 + 437*x_16 + 144*x_16^2 + 437*x_2' + 144*x_2'^2 + 437*x_22 + 144*x_22^2 }-> s41 :|: s35 >= 0, s35 <= 6 * x_1'', s36 >= 0, s36 <= 6 * x_2', s37 >= 0, s37 <= s35 + s36, s38 >= 0, s38 <= 6 * x_16, s39 >= 0, s39 <= 6 * x_22, s40 >= 0, s40 <= s38 + s39, s41 >= 0, s41 <= s37 + s40, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 12 + 2*s42 + s43 + 2*s44 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s45 :|: s42 >= 0, s42 <= 6 * x_1'', s43 >= 0, s43 <= 6 * x_2', s44 >= 0, s44 <= s42 + s43, s45 >= 0, s45 <= s44 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 7 + s46 + 437*x_17 + 144*x_17^2 }-> s47 :|: s46 >= 0, s46 <= 6 * x_17, s47 >= 0, s47 <= 0 + (1 + s46), x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 12 + 2*s48 + s49 + s50 + 437*x_18 + 144*x_18^2 + 437*x_23 + 144*x_23^2 }-> s51 :|: s48 >= 0, s48 <= 6 * x_18, s49 >= 0, s49 <= 6 * x_23, s50 >= 0, s50 <= s48 + s49, s51 >= 0, s51 <= 0 + s50, x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -290 + 149*z + 144*z^2 }-> 1 + s7 :|: s7 >= 0, s7 <= 6 * (z - 1), z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ -574 + 2*s52 + s53 + 149*z + 144*z^2 + 149*z' + 144*z'^2 }-> s54 :|: s52 >= 0, s52 <= 6 * (z - 1), s53 >= 0, s53 <= 6 * (z' - 1), s54 >= 0, s54 <= 1 + s52 + (1 + s53), z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s55 + 149*z + 144*z^2 }-> s56 :|: s55 >= 0, s55 <= 6 * (z - 1), s56 >= 0, s56 <= 1 + s55 + 0, z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ -276 + 2*s57 + 2*s58 + s59 + s60 + 437*x_112 + 144*x_112^2 + 437*x_25 + 144*x_25^2 + 149*z + 144*z^2 }-> s61 :|: s57 >= 0, s57 <= 6 * (z - 1), s58 >= 0, s58 <= 6 * x_112, s59 >= 0, s59 <= 6 * x_25, s60 >= 0, s60 <= s58 + s59, s61 >= 0, s61 <= 1 + s57 + s60, x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s62 + 149*z + 144*z^2 }-> s63 :|: s62 >= 0, s62 <= 6 * (z - 1), s63 >= 0, s63 <= 1 + s62 + 0, z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ -286 + s64 + 149*z' + 144*z'^2 }-> s65 :|: s64 >= 0, s64 <= 6 * (z' - 1), s65 >= 0, s65 <= 0 + (1 + s64), z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 12 + 2*s66 + s67 + s68 + 437*x_114 + 144*x_114^2 + 437*x_26 + 144*x_26^2 }-> s69 :|: s66 >= 0, s66 <= 6 * x_114, s67 >= 0, s67 <= 6 * x_26, s68 >= 0, s68 <= s66 + s67, s69 >= 0, s69 <= 0 + s68, x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ -277 + 2*s70 + s71 + 2*s72 + s73 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 + 149*z' + 144*z'^2 }-> s74 :|: s70 >= 0, s70 <= 6 * x_110, s71 >= 0, s71 <= 6 * x_24, s72 >= 0, s72 <= s70 + s71, s73 >= 0, s73 <= 6 * (z' - 1), s74 >= 0, s74 <= s72 + (1 + s73), z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s75 + s76 + 2*s77 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s78 :|: s75 >= 0, s75 <= 6 * x_110, s76 >= 0, s76 <= 6 * x_24, s77 >= 0, s77 <= s75 + s76, s78 >= 0, s78 <= s77 + 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 21 + 2*s79 + s80 + 2*s81 + 2*s82 + s83 + s84 + 437*x_110 + 144*x_110^2 + 437*x_116 + 144*x_116^2 + 437*x_24 + 144*x_24^2 + 437*x_27 + 144*x_27^2 }-> s85 :|: s79 >= 0, s79 <= 6 * x_110, s80 >= 0, s80 <= 6 * x_24, s81 >= 0, s81 <= s79 + s80, s82 >= 0, s82 <= 6 * x_116, s83 >= 0, s83 <= 6 * x_27, s84 >= 0, s84 <= s82 + s83, s85 >= 0, s85 <= s81 + s84, x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s86 + s87 + 2*s88 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s89 :|: s86 >= 0, s86 <= 6 * x_110, s87 >= 0, s87 <= 6 * x_24, s88 >= 0, s88 <= s86 + s87, s89 >= 0, s89 <= s88 + 0, z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ -286 + s90 + 149*z' + 144*z'^2 }-> s91 :|: s90 >= 0, s90 <= 6 * (z' - 1), s91 >= 0, s91 <= 0 + (1 + s90), z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 12 + 2*s92 + s93 + s94 + 437*x_118 + 144*x_118^2 + 437*x_28 + 144*x_28^2 }-> s95 :|: s92 >= 0, s92 <= 6 * x_118, s93 >= 0, s93 <= 6 * x_28, s94 >= 0, s94 <= s92 + s93, s95 >= 0, s95 <= 0 + s94, z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 3 + 437*z + 144*z^2 }-> 1 + s96 :|: s96 >= 0, s96 <= 6 * z, z >= 0

Function symbols to be analyzed: {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [6*z]
  encode_average: runtime: O(n^2) [81 + 4296*z + 1728*z^2 + 4230*z' + 1728*z'^2], size: O(n^1) [6*z + 6*z']

----------------------------------------

(47) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: encode_s
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 1 + 6*z

----------------------------------------

(48)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 12 + 2*s8 + s9 + 437*x_1' + 144*x_1'^2 + 437*x_11 + 144*x_11^2 }-> s10 :|: s8 >= 0, s8 <= 6 * x_1', s9 >= 0, s9 <= 6 * x_11, s10 >= 0, s10 <= 1 + s8 + (1 + s9), x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ -290 + 2*s11 + -139*z + 144*z^2 }-> s12 :|: s11 >= 0, s11 <= 6 * (z - 2), s12 >= 0, s12 <= 1 + s11 + 0, z - 2 >= 0
   encArg(z) -{ 17 + 2*s13 + 2*s14 + s15 + s16 + 437*x_1' + 144*x_1'^2 + 437*x_12 + 144*x_12^2 + 437*x_2'' + 144*x_2''^2 }-> s17 :|: s13 >= 0, s13 <= 6 * x_1', s14 >= 0, s14 <= 6 * x_12, s15 >= 0, s15 <= 6 * x_2'', s16 >= 0, s16 <= s14 + s15, s17 >= 0, s17 <= 1 + s13 + s16, z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 8 + 2*s18 + 437*x_1' + 144*x_1'^2 }-> s19 :|: s18 >= 0, s18 <= 6 * x_1', s19 >= 0, s19 <= 1 + s18 + 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ -291 + s20 + -139*z + 144*z^2 }-> s21 :|: s20 >= 0, s20 <= 6 * (z - 2), s21 >= 0, s21 <= 0 + (1 + s20), z - 2 >= 0
   encArg(z) -{ 12 + 2*s22 + s23 + s24 + 437*x_14 + 144*x_14^2 + 437*x_21 + 144*x_21^2 }-> s25 :|: s22 >= 0, s22 <= 6 * x_14, s23 >= 0, s23 <= 6 * x_21, s24 >= 0, s24 <= s22 + s23, s25 >= 0, s25 <= 0 + s24, x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 16 + 2*s26 + s27 + 2*s28 + s29 + 437*x_1'' + 144*x_1''^2 + 437*x_15 + 144*x_15^2 + 437*x_2' + 144*x_2'^2 }-> s30 :|: s26 >= 0, s26 <= 6 * x_1'', s27 >= 0, s27 <= 6 * x_2', s28 >= 0, s28 <= s26 + s27, s29 >= 0, s29 <= 6 * x_15, s30 >= 0, s30 <= s28 + (1 + s29), x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 12 + 2*s31 + s32 + 2*s33 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s34 :|: s31 >= 0, s31 <= 6 * x_1'', s32 >= 0, s32 <= 6 * x_2', s33 >= 0, s33 <= s31 + s32, s34 >= 0, s34 <= s33 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 21 + 2*s35 + s36 + 2*s37 + 2*s38 + s39 + s40 + 437*x_1'' + 144*x_1''^2 + 437*x_16 + 144*x_16^2 + 437*x_2' + 144*x_2'^2 + 437*x_22 + 144*x_22^2 }-> s41 :|: s35 >= 0, s35 <= 6 * x_1'', s36 >= 0, s36 <= 6 * x_2', s37 >= 0, s37 <= s35 + s36, s38 >= 0, s38 <= 6 * x_16, s39 >= 0, s39 <= 6 * x_22, s40 >= 0, s40 <= s38 + s39, s41 >= 0, s41 <= s37 + s40, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 12 + 2*s42 + s43 + 2*s44 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s45 :|: s42 >= 0, s42 <= 6 * x_1'', s43 >= 0, s43 <= 6 * x_2', s44 >= 0, s44 <= s42 + s43, s45 >= 0, s45 <= s44 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 7 + s46 + 437*x_17 + 144*x_17^2 }-> s47 :|: s46 >= 0, s46 <= 6 * x_17, s47 >= 0, s47 <= 0 + (1 + s46), x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 12 + 2*s48 + s49 + s50 + 437*x_18 + 144*x_18^2 + 437*x_23 + 144*x_23^2 }-> s51 :|: s48 >= 0, s48 <= 6 * x_18, s49 >= 0, s49 <= 6 * x_23, s50 >= 0, s50 <= s48 + s49, s51 >= 0, s51 <= 0 + s50, x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -290 + 149*z + 144*z^2 }-> 1 + s7 :|: s7 >= 0, s7 <= 6 * (z - 1), z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ -574 + 2*s52 + s53 + 149*z + 144*z^2 + 149*z' + 144*z'^2 }-> s54 :|: s52 >= 0, s52 <= 6 * (z - 1), s53 >= 0, s53 <= 6 * (z' - 1), s54 >= 0, s54 <= 1 + s52 + (1 + s53), z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s55 + 149*z + 144*z^2 }-> s56 :|: s55 >= 0, s55 <= 6 * (z - 1), s56 >= 0, s56 <= 1 + s55 + 0, z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ -276 + 2*s57 + 2*s58 + s59 + s60 + 437*x_112 + 144*x_112^2 + 437*x_25 + 144*x_25^2 + 149*z + 144*z^2 }-> s61 :|: s57 >= 0, s57 <= 6 * (z - 1), s58 >= 0, s58 <= 6 * x_112, s59 >= 0, s59 <= 6 * x_25, s60 >= 0, s60 <= s58 + s59, s61 >= 0, s61 <= 1 + s57 + s60, x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s62 + 149*z + 144*z^2 }-> s63 :|: s62 >= 0, s62 <= 6 * (z - 1), s63 >= 0, s63 <= 1 + s62 + 0, z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ -286 + s64 + 149*z' + 144*z'^2 }-> s65 :|: s64 >= 0, s64 <= 6 * (z' - 1), s65 >= 0, s65 <= 0 + (1 + s64), z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 12 + 2*s66 + s67 + s68 + 437*x_114 + 144*x_114^2 + 437*x_26 + 144*x_26^2 }-> s69 :|: s66 >= 0, s66 <= 6 * x_114, s67 >= 0, s67 <= 6 * x_26, s68 >= 0, s68 <= s66 + s67, s69 >= 0, s69 <= 0 + s68, x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ -277 + 2*s70 + s71 + 2*s72 + s73 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 + 149*z' + 144*z'^2 }-> s74 :|: s70 >= 0, s70 <= 6 * x_110, s71 >= 0, s71 <= 6 * x_24, s72 >= 0, s72 <= s70 + s71, s73 >= 0, s73 <= 6 * (z' - 1), s74 >= 0, s74 <= s72 + (1 + s73), z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s75 + s76 + 2*s77 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s78 :|: s75 >= 0, s75 <= 6 * x_110, s76 >= 0, s76 <= 6 * x_24, s77 >= 0, s77 <= s75 + s76, s78 >= 0, s78 <= s77 + 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 21 + 2*s79 + s80 + 2*s81 + 2*s82 + s83 + s84 + 437*x_110 + 144*x_110^2 + 437*x_116 + 144*x_116^2 + 437*x_24 + 144*x_24^2 + 437*x_27 + 144*x_27^2 }-> s85 :|: s79 >= 0, s79 <= 6 * x_110, s80 >= 0, s80 <= 6 * x_24, s81 >= 0, s81 <= s79 + s80, s82 >= 0, s82 <= 6 * x_116, s83 >= 0, s83 <= 6 * x_27, s84 >= 0, s84 <= s82 + s83, s85 >= 0, s85 <= s81 + s84, x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s86 + s87 + 2*s88 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s89 :|: s86 >= 0, s86 <= 6 * x_110, s87 >= 0, s87 <= 6 * x_24, s88 >= 0, s88 <= s86 + s87, s89 >= 0, s89 <= s88 + 0, z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ -286 + s90 + 149*z' + 144*z'^2 }-> s91 :|: s90 >= 0, s90 <= 6 * (z' - 1), s91 >= 0, s91 <= 0 + (1 + s90), z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 12 + 2*s92 + s93 + s94 + 437*x_118 + 144*x_118^2 + 437*x_28 + 144*x_28^2 }-> s95 :|: s92 >= 0, s92 <= 6 * x_118, s93 >= 0, s93 <= 6 * x_28, s94 >= 0, s94 <= s92 + s93, s95 >= 0, s95 <= 0 + s94, z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 3 + 437*z + 144*z^2 }-> 1 + s96 :|: s96 >= 0, s96 <= 6 * z, z >= 0

Function symbols to be analyzed: {encode_s}
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [6*z]
  encode_average: runtime: O(n^2) [81 + 4296*z + 1728*z^2 + 4230*z' + 1728*z'^2], size: O(n^1) [6*z + 6*z']
  encode_s: runtime: ?, size: O(n^1) [1 + 6*z]

----------------------------------------

(49) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: encode_s
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 3 + 437*z + 144*z^2

----------------------------------------

(50)
Obligation:
Complexity RNTS consisting of the following rules:

   average(z, z') -{ 3 + 2*z + z' }-> s :|: s >= 0, s <= z - 1 + (1 + z'), z - 1 >= 0, z' >= 0
   average(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0
   average(z, z') -{ 1 }-> 0 :|: z' = 1 + 0, z = 0
   average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   average(z, z') -{ 3 + 2*z + z' }-> 1 + s' :|: s' >= 0, s' <= 1 + z + (z' - 3), z >= 0, z' - 3 >= 0
   average(z, z') -{ 1 }-> 1 + 0 :|: z' = 1 + (1 + 0), z = 0
   encArg(z) -{ 3 }-> s'' :|: s'' >= 0, s'' <= 0 + 0, z = 1 + 0 + 0
   encArg(z) -{ 3 }-> s1 :|: s1 >= 0, s1 <= 0 + 0, z - 1 >= 0
   encArg(z) -{ 12 + 2*s8 + s9 + 437*x_1' + 144*x_1'^2 + 437*x_11 + 144*x_11^2 }-> s10 :|: s8 >= 0, s8 <= 6 * x_1', s9 >= 0, s9 <= 6 * x_11, s10 >= 0, s10 <= 1 + s8 + (1 + s9), x_11 >= 0, x_1' >= 0, z = 1 + (1 + x_1') + (1 + x_11)
   encArg(z) -{ -290 + 2*s11 + -139*z + 144*z^2 }-> s12 :|: s11 >= 0, s11 <= 6 * (z - 2), s12 >= 0, s12 <= 1 + s11 + 0, z - 2 >= 0
   encArg(z) -{ 17 + 2*s13 + 2*s14 + s15 + s16 + 437*x_1' + 144*x_1'^2 + 437*x_12 + 144*x_12^2 + 437*x_2'' + 144*x_2''^2 }-> s17 :|: s13 >= 0, s13 <= 6 * x_1', s14 >= 0, s14 <= 6 * x_12, s15 >= 0, s15 <= 6 * x_2'', s16 >= 0, s16 <= s14 + s15, s17 >= 0, s17 <= 1 + s13 + s16, z = 1 + (1 + x_1') + (1 + x_12 + x_2''), x_1' >= 0, x_2'' >= 0, x_12 >= 0
   encArg(z) -{ 8 + 2*s18 + 437*x_1' + 144*x_1'^2 }-> s19 :|: s18 >= 0, s18 <= 6 * x_1', s19 >= 0, s19 <= 1 + s18 + 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2
   encArg(z) -{ 3 }-> s2 :|: s2 >= 0, s2 <= 0 + 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0
   encArg(z) -{ -291 + s20 + -139*z + 144*z^2 }-> s21 :|: s20 >= 0, s20 <= 6 * (z - 2), s21 >= 0, s21 <= 0 + (1 + s20), z - 2 >= 0
   encArg(z) -{ 12 + 2*s22 + s23 + s24 + 437*x_14 + 144*x_14^2 + 437*x_21 + 144*x_21^2 }-> s25 :|: s22 >= 0, s22 <= 6 * x_14, s23 >= 0, s23 <= 6 * x_21, s24 >= 0, s24 <= s22 + s23, s25 >= 0, s25 <= 0 + s24, x_14 >= 0, z = 1 + 0 + (1 + x_14 + x_21), x_21 >= 0
   encArg(z) -{ 16 + 2*s26 + s27 + 2*s28 + s29 + 437*x_1'' + 144*x_1''^2 + 437*x_15 + 144*x_15^2 + 437*x_2' + 144*x_2'^2 }-> s30 :|: s26 >= 0, s26 <= 6 * x_1'', s27 >= 0, s27 <= 6 * x_2', s28 >= 0, s28 <= s26 + s27, s29 >= 0, s29 <= 6 * x_15, s30 >= 0, s30 <= s28 + (1 + s29), x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0
   encArg(z) -{ 12 + 2*s31 + s32 + 2*s33 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s34 :|: s31 >= 0, s31 <= 6 * x_1'', s32 >= 0, s32 <= 6 * x_2', s33 >= 0, s33 <= s31 + s32, s34 >= 0, s34 <= s33 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + 0
   encArg(z) -{ 21 + 2*s35 + s36 + 2*s37 + 2*s38 + s39 + s40 + 437*x_1'' + 144*x_1''^2 + 437*x_16 + 144*x_16^2 + 437*x_2' + 144*x_2'^2 + 437*x_22 + 144*x_22^2 }-> s41 :|: s35 >= 0, s35 <= 6 * x_1'', s36 >= 0, s36 <= 6 * x_2', s37 >= 0, s37 <= s35 + s36, s38 >= 0, s38 <= 6 * x_16, s39 >= 0, s39 <= 6 * x_22, s40 >= 0, s40 <= s38 + s39, s41 >= 0, s41 <= s37 + s40, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_22), x_22 >= 0
   encArg(z) -{ 12 + 2*s42 + s43 + 2*s44 + 437*x_1'' + 144*x_1''^2 + 437*x_2' + 144*x_2'^2 }-> s45 :|: s42 >= 0, s42 <= 6 * x_1'', s43 >= 0, s43 <= 6 * x_2', s44 >= 0, s44 <= s42 + s43, s45 >= 0, s45 <= s44 + 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0
   encArg(z) -{ 7 + s46 + 437*x_17 + 144*x_17^2 }-> s47 :|: s46 >= 0, s46 <= 6 * x_17, s47 >= 0, s47 <= 0 + (1 + s46), x_1 >= 0, x_17 >= 0, z = 1 + x_1 + (1 + x_17)
   encArg(z) -{ 12 + 2*s48 + s49 + s50 + 437*x_18 + 144*x_18^2 + 437*x_23 + 144*x_23^2 }-> s51 :|: s48 >= 0, s48 <= 6 * x_18, s49 >= 0, s49 <= 6 * x_23, s50 >= 0, s50 <= s48 + s49, s51 >= 0, s51 <= 0 + s50, x_1 >= 0, z = 1 + x_1 + (1 + x_18 + x_23), x_23 >= 0, x_18 >= 0
   encArg(z) -{ 0 }-> 0 :|: z = 0
   encArg(z) -{ 0 }-> 0 :|: z >= 0
   encArg(z) -{ -290 + 149*z + 144*z^2 }-> 1 + s7 :|: s7 >= 0, s7 <= 6 * (z - 1), z - 1 >= 0
   encode_0 -{ 0 }-> 0 :|: 
   encode_average(z, z') -{ 3 }-> s3 :|: s3 >= 0, s3 <= 0 + 0, z = 0, z' = 0
   encode_average(z, z') -{ 3 }-> s4 :|: s4 >= 0, s4 <= 0 + 0, z' >= 0, z = 0
   encode_average(z, z') -{ 3 }-> s5 :|: s5 >= 0, s5 <= 0 + 0, z >= 0, z' = 0
   encode_average(z, z') -{ -574 + 2*s52 + s53 + 149*z + 144*z^2 + 149*z' + 144*z'^2 }-> s54 :|: s52 >= 0, s52 <= 6 * (z - 1), s53 >= 0, s53 <= 6 * (z' - 1), s54 >= 0, s54 <= 1 + s52 + (1 + s53), z - 1 >= 0, z' - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s55 + 149*z + 144*z^2 }-> s56 :|: s55 >= 0, s55 <= 6 * (z - 1), s56 >= 0, s56 <= 1 + s55 + 0, z' = 0, z - 1 >= 0
   encode_average(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + 0, z >= 0, z' >= 0
   encode_average(z, z') -{ -276 + 2*s57 + 2*s58 + s59 + s60 + 437*x_112 + 144*x_112^2 + 437*x_25 + 144*x_25^2 + 149*z + 144*z^2 }-> s61 :|: s57 >= 0, s57 <= 6 * (z - 1), s58 >= 0, s58 <= 6 * x_112, s59 >= 0, s59 <= 6 * x_25, s60 >= 0, s60 <= s58 + s59, s61 >= 0, s61 <= 1 + s57 + s60, x_25 >= 0, z' = 1 + x_112 + x_25, x_112 >= 0, z - 1 >= 0
   encode_average(z, z') -{ -285 + 2*s62 + 149*z + 144*z^2 }-> s63 :|: s62 >= 0, s62 <= 6 * (z - 1), s63 >= 0, s63 <= 1 + s62 + 0, z' >= 0, z - 1 >= 0
   encode_average(z, z') -{ -286 + s64 + 149*z' + 144*z'^2 }-> s65 :|: s64 >= 0, s64 <= 6 * (z' - 1), s65 >= 0, s65 <= 0 + (1 + s64), z' - 1 >= 0, z = 0
   encode_average(z, z') -{ 12 + 2*s66 + s67 + s68 + 437*x_114 + 144*x_114^2 + 437*x_26 + 144*x_26^2 }-> s69 :|: s66 >= 0, s66 <= 6 * x_114, s67 >= 0, s67 <= 6 * x_26, s68 >= 0, s68 <= s66 + s67, s69 >= 0, s69 <= 0 + s68, x_114 >= 0, x_26 >= 0, z' = 1 + x_114 + x_26, z = 0
   encode_average(z, z') -{ -277 + 2*s70 + s71 + 2*s72 + s73 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 + 149*z' + 144*z'^2 }-> s74 :|: s70 >= 0, s70 <= 6 * x_110, s71 >= 0, s71 <= 6 * x_24, s72 >= 0, s72 <= s70 + s71, s73 >= 0, s73 <= 6 * (z' - 1), s74 >= 0, s74 <= s72 + (1 + s73), z' - 1 >= 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s75 + s76 + 2*s77 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s78 :|: s75 >= 0, s75 <= 6 * x_110, s76 >= 0, s76 <= 6 * x_24, s77 >= 0, s77 <= s75 + s76, s78 >= 0, s78 <= s77 + 0, z = 1 + x_110 + x_24, x_24 >= 0, x_110 >= 0, z' = 0
   encode_average(z, z') -{ 21 + 2*s79 + s80 + 2*s81 + 2*s82 + s83 + s84 + 437*x_110 + 144*x_110^2 + 437*x_116 + 144*x_116^2 + 437*x_24 + 144*x_24^2 + 437*x_27 + 144*x_27^2 }-> s85 :|: s79 >= 0, s79 <= 6 * x_110, s80 >= 0, s80 <= 6 * x_24, s81 >= 0, s81 <= s79 + s80, s82 >= 0, s82 <= 6 * x_116, s83 >= 0, s83 <= 6 * x_27, s84 >= 0, s84 <= s82 + s83, s85 >= 0, s85 <= s81 + s84, x_116 >= 0, z' = 1 + x_116 + x_27, z = 1 + x_110 + x_24, x_24 >= 0, x_27 >= 0, x_110 >= 0
   encode_average(z, z') -{ 12 + 2*s86 + s87 + 2*s88 + 437*x_110 + 144*x_110^2 + 437*x_24 + 144*x_24^2 }-> s89 :|: s86 >= 0, s86 <= 6 * x_110, s87 >= 0, s87 <= 6 * x_24, s88 >= 0, s88 <= s86 + s87, s89 >= 0, s89 <= s88 + 0, z = 1 + x_110 + x_24, x_24 >= 0, z' >= 0, x_110 >= 0
   encode_average(z, z') -{ -286 + s90 + 149*z' + 144*z'^2 }-> s91 :|: s90 >= 0, s90 <= 6 * (z' - 1), s91 >= 0, s91 <= 0 + (1 + s90), z >= 0, z' - 1 >= 0
   encode_average(z, z') -{ 12 + 2*s92 + s93 + s94 + 437*x_118 + 144*x_118^2 + 437*x_28 + 144*x_28^2 }-> s95 :|: s92 >= 0, s92 <= 6 * x_118, s93 >= 0, s93 <= 6 * x_28, s94 >= 0, s94 <= s92 + s93, s95 >= 0, s95 <= 0 + s94, z >= 0, z' = 1 + x_118 + x_28, x_118 >= 0, x_28 >= 0
   encode_average(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
   encode_s(z) -{ 0 }-> 0 :|: z >= 0
   encode_s(z) -{ 3 + 437*z + 144*z^2 }-> 1 + s96 :|: s96 >= 0, s96 <= 6 * z, z >= 0

Function symbols to be analyzed: 
Previous analysis results are:
  encode_0: runtime: O(1) [0], size: O(1) [0]
  average: runtime: O(n^1) [3 + 2*z + z'], size: O(n^1) [z + z']
  encArg: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [6*z]
  encode_average: runtime: O(n^2) [81 + 4296*z + 1728*z^2 + 4230*z' + 1728*z'^2], size: O(n^1) [6*z + 6*z']
  encode_s: runtime: O(n^2) [3 + 437*z + 144*z^2], size: O(n^1) [1 + 6*z]

----------------------------------------

(51) FinalProof (FINISHED)
Computed overall runtime complexity
----------------------------------------

(52)
BOUNDS(1, n^2)

----------------------------------------

(53) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(54)
Obligation:
Analyzing the following TRS for decreasing loops:

The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y))
   average(x, s(s(s(y)))) -> s(average(s(x), y))
   average(0, 0) -> 0
   average(0, s(0)) -> 0
   average(0, s(s(0))) -> s(0)

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

Rewrite Strategy: FULL
----------------------------------------

(55) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

average(s(x), y) ->^+ average(x, s(y))

gives rise to a decreasing loop by considering the right hand sides subterm at position [].

The pumping substitution is [x / s(x)].

The result substitution is [y / s(y)].




----------------------------------------

(56)
Complex Obligation (BEST)

----------------------------------------

(57)
Obligation:
Proved the lower bound n^1 for the following obligation:

The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y))
   average(x, s(s(s(y)))) -> s(average(s(x), y))
   average(0, 0) -> 0
   average(0, s(0)) -> 0
   average(0, s(s(0))) -> s(0)

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

Rewrite Strategy: FULL
----------------------------------------

(58) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(59)
BOUNDS(n^1, INF)

----------------------------------------

(60)
Obligation:
Analyzing the following TRS for decreasing loops:

The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2).


The TRS R consists of the following rules:

   average(s(x), y) -> average(x, s(y))
   average(x, s(s(s(y)))) -> s(average(s(x), y))
   average(0, 0) -> 0
   average(0, s(0)) -> 0
   average(0, s(s(0))) -> s(0)

The (relative) TRS S consists of the following rules:

   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(0) -> 0
   encArg(cons_average(x_1, x_2)) -> average(encArg(x_1), encArg(x_2))
   encode_average(x_1, x_2) -> average(encArg(x_1), encArg(x_2))
   encode_s(x_1) -> s(encArg(x_1))
   encode_0 -> 0

Rewrite Strategy: FULL