Inferring Expected Runtimes Using Sizes

KoAT2 Proof WORST_CASE( ?, 2+2*(2+Arg_0+Arg_1)+3*(1+Arg_0+Arg_1)+3*(Arg_0+Arg_1)+Arg_0+Arg_1 {O(n)})

Initial Complexity Problem (after preprocessing)

Start:f
Program_Vars:Arg_0, Arg_1, Arg_2
Temp_Vars:
Locations:f, g, h, i
Transitions:
f(Arg_0,Arg_1,Arg_2) -{0}> g(Arg_0,Arg_1,Arg_2)
h(Arg_0,Arg_1,Arg_2) -{0}> i(Arg_1,Arg_1,Arg_0) :|: 0<=2+Arg_0 && 0<=2+Arg_0
i(Arg_0,Arg_1,Arg_2) -> g(Arg_0,Arg_2,Arg_2) :|: 0<=2+Arg_2 && Arg_1<=Arg_0 && Arg_0<=Arg_1 && 0<=2+Arg_2 && Arg_1<=Arg_0 && Arg_0<=Arg_1
f(Arg_0,Arg_1,Arg_2) -{0}> 1/3:h(Arg_0-3,Arg_1,Arg_2) :+: 1/3:h(Arg_0-2,Arg_1,Arg_2) :+: 1/3:h(Arg_0-1,Arg_1,Arg_2) :|: 0<Arg_0
i(Arg_0,Arg_1,Arg_2) -> 1/3:h(Arg_0-3,Arg_2,Arg_2) :+: 1/3:h(Arg_0-2,Arg_2,Arg_2) :+: 1/3:h(Arg_0-1,Arg_2,Arg_2) :|: 0<=2+Arg_2 && Arg_1<=Arg_0 && Arg_0<=Arg_1 && 0<Arg_0 && 0<=2+Arg_2 && Arg_1<=Arg_0 && Arg_0<=Arg_1

G f f g g f->g t₀ ∈ g₀ {0} h h f->h t₆ ∈ g₄ p = 1/3 η (Arg_0) = Arg_0-3 τ = 0<Arg_0 {0} f->h t₇ ∈ g₄ p = 1/3 η (Arg_0) = Arg_0-2 τ = 0<Arg_0 {0} f->h t₈ ∈ g₄ p = 1/3 η (Arg_0) = Arg_0-1 τ = 0<Arg_0 {0} i i h->i t₄ ∈ g₂ η (Arg_0) = Arg_1 η (Arg_2) = Arg_0 {0} i->g t₅ ∈ g₃ η (Arg_1) = Arg_2 i->h t₉ ∈ g₅ p = 1/3 η (Arg_0) = Arg_0-3 η (Arg_1) = Arg_2 τ = 0<Arg_0 i->h t₁₀ ∈ g₅ p = 1/3 η (Arg_0) = Arg_0-2 η (Arg_1) = Arg_2 τ = 0<Arg_0 i->h t₁₁ ∈ g₅ p = 1/3 η (Arg_0) = Arg_0-1 η (Arg_1) = Arg_2 τ = 0<Arg_0

Timebounds:

Overall timebound:2*max([(-1)+Arg_0+Arg_1, 0])+4*max([0, 2+Arg_0+Arg_1])+6*max([0, 1+Arg_0+Arg_1])+8+6*max([0, Arg_0+Arg_1]) {O(n)}
0,0: f->g: 1 {O(1)}
6,4: f->h: 1 {O(1)}
7,4: f->h: 1 {O(1)}
8,4: f->h: 1 {O(1)}
4,2: h->i: 2*max([0, 2+Arg_0+Arg_1])+3+3*max([0, 1+Arg_0+Arg_1])+3*max([0, Arg_0+Arg_1])+max([(-1)+Arg_0+Arg_1, 0]) {O(n)}
5,3: i->g: 1 {O(1)}
9,5: i->h: max([0, 1+Arg_0+Arg_1])+max([0, 2+Arg_0+Arg_1])+max([0, Arg_0+Arg_1]) {O(n)}
10,5: i->h: max([0, 1+Arg_0+Arg_1])+max([0, 2+Arg_0+Arg_1])+max([0, Arg_0+Arg_1]) {O(n)}
11,5: i->h: max([(-1)+Arg_0+Arg_1, 0])+max([0, 1+Arg_0+Arg_1])+max([0, Arg_0+Arg_1]) {O(n)}

Expected Timebounds:

Overall expected timebound: 2*Arg_0+2*Arg_1+4*(2+Arg_0+Arg_1)+6*(1+Arg_0+Arg_1)+8+6*(Arg_0+Arg_1) {O(n)}
0: f->[1:g]: 1 {O(1)}
2: h->[1:i]: 2*(2+Arg_0+Arg_1)+3*(1+Arg_0+Arg_1)+3*(Arg_0+Arg_1)+4+Arg_0+Arg_1 {O(n)}
3: i->[1:g]: 1 {O(1)}
4: f->[1/3:h; 1/3:h; 1/3:h]: 1 {O(1)}
5: i->[1/3:h; 1/3:h; 1/3:h]: 1+2*(2+Arg_0+Arg_1)+3*(1+Arg_0+Arg_1)+3*(Arg_0+Arg_1)+Arg_0+Arg_1 {O(n)}

Costbounds:

Overall costbound: inf {Infinity}
0,0: f->g: inf {Infinity}
6,4: f->h: inf {Infinity}
7,4: f->h: inf {Infinity}
8,4: f->h: inf {Infinity}
4,2: h->i: inf {Infinity}
5,3: i->g: inf {Infinity}
9,5: i->h: inf {Infinity}
10,5: i->h: inf {Infinity}
11,5: i->h: inf {Infinity}

Expected Costbounds:

Overall expected costbound: 2+2*(2+Arg_0+Arg_1)+3*(1+Arg_0+Arg_1)+3*(Arg_0+Arg_1)+Arg_0+Arg_1 {O(n)}
0: f->[1:g]: 0 {O(1)}
2: h->[1:i]: 0 {O(1)}
3: i->[1:g]: 1 {O(1)}
4: f->[1/3:h; 1/3:h; 1/3:h]: 0 {O(1)}
5: i->[1/3:h; 1/3:h; 1/3:h]: 1+2*(2+Arg_0+Arg_1)+3*(1+Arg_0+Arg_1)+3*(Arg_0+Arg_1)+Arg_0+Arg_1 {O(n)}

Sizebounds:

0,0: f->g, Arg_0: Arg_0 {O(n)}
0,0: f->g, Arg_1: Arg_1 {O(n)}
0,0: f->g, Arg_2: Arg_2 {O(n)}
6,4: f->h, Arg_0: (-3)+Arg_0 {O(n)}
6,4: f->h, Arg_1: Arg_1 {O(n)}
6,4: f->h, Arg_2: Arg_2 {O(n)}
7,4: f->h, Arg_0: (-2)+Arg_0 {O(n)}
7,4: f->h, Arg_1: Arg_1 {O(n)}
7,4: f->h, Arg_2: Arg_2 {O(n)}
8,4: f->h, Arg_0: (-1)+Arg_0 {O(n)}
8,4: f->h, Arg_1: Arg_1 {O(n)}
8,4: f->h, Arg_2: Arg_2 {O(n)}
4,2: h->i, Arg_0: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
4,2: h->i, Arg_1: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
4,2: h->i, Arg_2: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
5,3: i->g, Arg_0: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
5,3: i->g, Arg_1: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
5,3: i->g, Arg_2: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
9,5: i->h, Arg_0: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
9,5: i->h, Arg_1: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
9,5: i->h, Arg_2: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
10,5: i->h, Arg_0: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
10,5: i->h, Arg_1: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
10,5: i->h, Arg_2: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
11,5: i->h, Arg_0: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
11,5: i->h, Arg_1: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}
11,5: i->h, Arg_2: max([max([max([(-1)+Arg_0, (-2)+Arg_0]), (-3)+Arg_0]), Arg_1]) {O(n)}

ExpSizeBounds:

(0: f->[1:g], g), Arg_0: Arg_0 {O(n)}
(0: f->[1:g], g), Arg_1: Arg_1 {O(n)}
(0: f->[1:g], g), Arg_2: Arg_2 {O(n)}
(2: h->[1:i], i), Arg_0: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(2: h->[1:i], i), Arg_1: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(2: h->[1:i], i), Arg_2: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(3: i->[1:g], g), Arg_0: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(3: i->[1:g], g), Arg_1: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(3: i->[1:g], g), Arg_2: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(4: f->[1/3:h; 1/3:h; 1/3:h], h), Arg_0: 2+Arg_0 {O(n)}
(4: f->[1/3:h; 1/3:h; 1/3:h], h), Arg_1: Arg_1 {O(n)}
(4: f->[1/3:h; 1/3:h; 1/3:h], h), Arg_2: Arg_2 {O(n)}
(5: i->[1/3:h; 1/3:h; 1/3:h], h), Arg_0: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(5: i->[1/3:h; 1/3:h; 1/3:h], h), Arg_1: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}
(5: i->[1/3:h; 1/3:h; 1/3:h], h), Arg_2: max([max([max([1+Arg_0, 2+Arg_0]), 3+Arg_0]), Arg_1]) {O(n)}