/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files


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


WORST_CASE(?, O(n^1))
proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, max(3 + 8 * Arg_0, 11, 11 + 8 * Arg_2)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 213 ms]
(2) BOUNDS(1, max(3 + 8 * Arg_0, 11, 11 + 8 * Arg_2))


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f0(A, B, C) -> Com_1(f2(A, D, C)) :|: 0 >= A
f0(A, B, C) -> Com_1(f0(A + C, B, -(1) + C)) :|: A >= 1
f1(A, B, C) -> Com_1(f0(A, B, C)) :|: TRUE

The start-symbols are:[f1_3]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 3+8*max([1, max([Arg_0, 1+Arg_2])]) {O(n)})



Initial Complexity Problem:

  Start:  f1  

  Program_Vars:  Arg_0, Arg_1, Arg_2  

  Temp_Vars:  D  

  Locations:  f0, f1, f2  

  Transitions:

  1: f0->f0

  0: f0->f2

  2: f1->f0  



Timebounds: 

  Overall timebound: 3+8*max([1, max([Arg_0, 1+Arg_2])]) {O(n)}

  0: f0->f2: 1 {O(1)}

  1: f0->f0: 1+8*max([1, max([Arg_0, 1+Arg_2])]) {O(n)}

  2: f1->f0: 1 {O(1)}



Costbounds:

  Overall costbound: 3+8*max([1, max([Arg_0, 1+Arg_2])]) {O(n)}

  0: f0->f2: 1 {O(1)}

  1: f0->f0: 1+8*max([1, max([Arg_0, 1+Arg_2])]) {O(n)}

  2: f1->f0: 1 {O(1)}



Sizebounds:

`Lower:

  0: f0->f2, Arg_0: min([Arg_0, min([-(-1-Arg_2), -(-(Arg_2)+8*max([1, max([Arg_0, 1+Arg_2])]))])]) {O(n)}

  0: f0->f2, Arg_2: min([Arg_2, -(1+-(Arg_2)+8*max([1, max([Arg_0, 1+Arg_2])]))]) {O(n)}

  1: f0->f0, Arg_0: min([-(-1-Arg_2), -(-(Arg_2)+8*max([1, max([Arg_0, 1+Arg_2])]))]) {O(n)}

  1: f0->f0, Arg_1: Arg_1 {O(n)}

  1: f0->f0, Arg_2: -1+Arg_2+-8*max([1, max([Arg_0, 1+Arg_2])]) {O(n)}

  2: f1->f0, Arg_0: Arg_0 {O(n)}

  2: f1->f0, Arg_1: Arg_1 {O(n)}

  2: f1->f0, Arg_2: Arg_2 {O(n)}

`Upper:

  0: f0->f2, Arg_0: 0 {O(1)}

  0: f0->f2, Arg_2: Arg_2 {O(n)}

  1: f0->f0, Arg_0: (1+8*max([1, max([Arg_0, 1+Arg_2])]))*max([0, Arg_2])+max([Arg_2, max([Arg_2, Arg_0])]) {O(n^2)}

  1: f0->f0, Arg_1: Arg_1 {O(n)}

  1: f0->f0, Arg_2: Arg_2 {O(n)}

  2: f1->f0, Arg_0: Arg_0 {O(n)}

  2: f1->f0, Arg_1: Arg_1 {O(n)}

  2: f1->f0, Arg_2: Arg_2 {O(n)}


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

(2)
BOUNDS(1, max(3 + 8 * Arg_0, 11, 11 + 8 * Arg_2))