Inferring Expected Runtimes Using Sizes

KoAT2 Proof WORST_CASE( ?, 9*Arg_2 {O(n)})

Initial Complexity Problem (after preprocessing)

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

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

Timebounds:

Overall timebound:inf {Infinity}
0,0: f->g: 1 {O(1)}
1,1: g->h: max([0, 1+Arg_2]) {O(n)}
2,1: g->g: max([0, 3*Arg_2]) {O(n)}
3,2: h->i: max([0, Arg_2]) {O(n)}
4,2: h->j: inf {Infinity}
5,2: h->k: inf {Infinity}
6,3: h->g: max([0, 4*Arg_2]) {O(n)}
7,4: i->h: max([0, Arg_2]) {O(n)}
8,5: j->h: inf {Infinity}
9,6: k->h: inf {Infinity}

Expected Timebounds:

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

Costbounds:

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

Expected Costbounds:

Overall expected costbound: 9*Arg_2 {O(n)}
0: f->[1:g]: 0 {O(1)}
1: g->[1/2:h; 1/2:g]: 0 {O(1)}
2: h->[1/3:i; 1/3:j; 1/3:k]: 0 {O(1)}
3: h->[1:g]: 0 {O(1)}
4: i->[1:h]: 3*Arg_2 {O(n)}
5: j->[1:h]: 5/2*Arg_2 {O(n)}
6: k->[1:h]: 7/2*Arg_2 {O(n)}

Sizebounds:

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

ExpSizeBounds:

(0: f->[1:g], g), Arg_0: 0 {O(1)}
(0: f->[1:g], g), Arg_1: Arg_1 {O(n)}
(0: f->[1:g], g), Arg_2: Arg_2 {O(n)}
(1: g->[1/2:h; 1/2:g], g), Arg_0: 7/2*Arg_2 {O(n)}
(1: g->[1/2:h; 1/2:g], g), Arg_1: 1/2*Arg_1 {O(n)}
(1: g->[1/2:h; 1/2:g], g), Arg_2: Arg_2 {O(n)}
(1: g->[1/2:h; 1/2:g], h), Arg_0: 7/2*Arg_2 {O(n)}
(1: g->[1/2:h; 1/2:g], h), Arg_1: 1/2 {O(1)}
(1: g->[1/2:h; 1/2:g], h), Arg_2: Arg_2 {O(n)}
(2: h->[1/3:i; 1/3:j; 1/3:k], i), Arg_0: 7/3*Arg_2 {O(n)}
(2: h->[1/3:i; 1/3:j; 1/3:k], i), Arg_1: 1/3 {O(1)}
(2: h->[1/3:i; 1/3:j; 1/3:k], i), Arg_2: Arg_2 {O(n)}
(2: h->[1/3:i; 1/3:j; 1/3:k], j), Arg_0: 7/3*Arg_2 {O(n)}
(2: h->[1/3:i; 1/3:j; 1/3:k], j), Arg_1: 1/3 {O(1)}
(2: h->[1/3:i; 1/3:j; 1/3:k], j), Arg_2: Arg_2 {O(n)}
(2: h->[1/3:i; 1/3:j; 1/3:k], k), Arg_0: 7/3*Arg_2 {O(n)}
(2: h->[1/3:i; 1/3:j; 1/3:k], k), Arg_1: 1/3 {O(1)}
(2: h->[1/3:i; 1/3:j; 1/3:k], k), Arg_2: Arg_2 {O(n)}
(3: h->[1:g], g), Arg_0: 7*Arg_2 {O(n)}
(3: h->[1:g], g), Arg_1: 0 {O(1)}
(3: h->[1:g], g), Arg_2: Arg_2 {O(n)}
(4: i->[1:h], h), Arg_0: 7*Arg_2 {O(n)}
(4: i->[1:h], h), Arg_1: 0 {O(1)}
(4: i->[1:h], h), Arg_2: Arg_2 {O(n)}
(5: j->[1:h], h), Arg_0: 7*Arg_2 {O(n)}
(5: j->[1:h], h), Arg_1: 1 {O(1)}
(5: j->[1:h], h), Arg_2: Arg_2 {O(n)}
(6: k->[1:h], h), Arg_0: 7*Arg_2 {O(n)}
(6: k->[1:h], h), Arg_1: 1 {O(1)}
(6: k->[1:h], h), Arg_2: Arg_2 {O(n)}