Inferring Expected Runtimes Using Sizes

KoAT2 Proof WORST_CASE( ?, (1+Arg_2)*(2*(1+Arg_2)+2*Arg_2)+3*Arg_2+4+4*(1+Arg_2)*Arg_2 {O(n^2)})

Initial Complexity Problem (after preprocessing)

Start:f0
Program_Vars:Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5, Arg_6, Arg_7
Temp_Vars:I
Locations:f0, f10, f18, f22, f34
Transitions:
f0(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> f10(I,0,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7)
f10(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> f10(Arg_0,Arg_1+1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) :|: Arg_1+1<=Arg_2 && 0<=Arg_1
f18(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_4,Arg_4+1,Arg_7) :|: 2+Arg_4<=Arg_3 && Arg_4<=Arg_1 && 0<=Arg_4 && 0<=Arg_1+Arg_4 && Arg_3<=Arg_2 && Arg_3<=Arg_1 && Arg_2<=Arg_3 && Arg_2<=Arg_1 && 0<=Arg_1
f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> 1/2:f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6+1,Arg_7) :+: 1/2:f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) :|: Arg_6+1<=Arg_3 && Arg_6<=Arg_3 && Arg_6<=Arg_2 && Arg_6<=Arg_1 && 1<=Arg_6 && 1<=Arg_5+Arg_6 && 1+Arg_5<=Arg_6 && 1<=Arg_4+Arg_6 && 1+Arg_4<=Arg_6 && 3<=Arg_3+Arg_6 && 3<=Arg_2+Arg_6 && 3<=Arg_1+Arg_6 && 1+Arg_5<=Arg_3 && 1+Arg_5<=Arg_2 && 1+Arg_5<=Arg_1 && 0<=Arg_5 && 0<=Arg_4+Arg_5 && Arg_4<=Arg_5 && 2<=Arg_3+Arg_5 && 2<=Arg_2+Arg_5 && 2<=Arg_1+Arg_5 && 2+Arg_4<=Arg_3 && 2+Arg_4<=Arg_2 && 2+Arg_4<=Arg_1 && 0<=Arg_4 && 2<=Arg_3+Arg_4 && 2<=Arg_2+Arg_4 && 2<=Arg_1+Arg_4 && Arg_3<=Arg_2 && Arg_3<=Arg_1 && 2<=Arg_3 && 4<=Arg_2+Arg_3 && Arg_2<=Arg_3 && 4<=Arg_1+Arg_3 && Arg_2<=Arg_1 && 2<=Arg_2 && 4<=Arg_1+Arg_2 && 2<=Arg_1
f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> 1/2:f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_6,Arg_6+1,Arg_7) :+: 1/2:f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) :|: Arg_6+1<=Arg_3 && Arg_6<=Arg_3 && Arg_6<=Arg_2 && Arg_6<=Arg_1 && 1<=Arg_6 && 1<=Arg_5+Arg_6 && 1+Arg_5<=Arg_6 && 1<=Arg_4+Arg_6 && 1+Arg_4<=Arg_6 && 3<=Arg_3+Arg_6 && 3<=Arg_2+Arg_6 && 3<=Arg_1+Arg_6 && 1+Arg_5<=Arg_3 && 1+Arg_5<=Arg_2 && 1+Arg_5<=Arg_1 && 0<=Arg_5 && 0<=Arg_4+Arg_5 && Arg_4<=Arg_5 && 2<=Arg_3+Arg_5 && 2<=Arg_2+Arg_5 && 2<=Arg_1+Arg_5 && 2+Arg_4<=Arg_3 && 2+Arg_4<=Arg_2 && 2+Arg_4<=Arg_1 && 0<=Arg_4 && 2<=Arg_3+Arg_4 && 2<=Arg_2+Arg_4 && 2<=Arg_1+Arg_4 && Arg_3<=Arg_2 && Arg_3<=Arg_1 && 2<=Arg_3 && 4<=Arg_2+Arg_3 && Arg_2<=Arg_3 && 4<=Arg_1+Arg_3 && Arg_2<=Arg_1 && 2<=Arg_2 && 4<=Arg_1+Arg_2 && 2<=Arg_1
f22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> f18(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4+1,Arg_5,Arg_6,I) :|: Arg_3<=Arg_6 && Arg_6<=Arg_3 && Arg_6<=Arg_2 && Arg_6<=Arg_1 && 1<=Arg_6 && 1<=Arg_5+Arg_6 && 1+Arg_5<=Arg_6 && 1<=Arg_4+Arg_6 && 1+Arg_4<=Arg_6 && 3<=Arg_3+Arg_6 && 3<=Arg_2+Arg_6 && 3<=Arg_1+Arg_6 && 1+Arg_5<=Arg_3 && 1+Arg_5<=Arg_2 && 1+Arg_5<=Arg_1 && 0<=Arg_5 && 0<=Arg_4+Arg_5 && Arg_4<=Arg_5 && 2<=Arg_3+Arg_5 && 2<=Arg_2+Arg_5 && 2<=Arg_1+Arg_5 && 2+Arg_4<=Arg_3 && 2+Arg_4<=Arg_2 && 2+Arg_4<=Arg_1 && 0<=Arg_4 && 2<=Arg_3+Arg_4 && 2<=Arg_2+Arg_4 && 2<=Arg_1+Arg_4 && Arg_3<=Arg_2 && Arg_3<=Arg_1 && 2<=Arg_3 && 4<=Arg_2+Arg_3 && Arg_2<=Arg_3 && 4<=Arg_1+Arg_3 && Arg_2<=Arg_1 && 2<=Arg_2 && 4<=Arg_1+Arg_2 && 2<=Arg_1
f18(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> f34(Arg_0,Arg_1,Arg_2,Arg_3,0,Arg_5,Arg_6,Arg_7) :|: Arg_3<=Arg_4+1 && Arg_4<=Arg_1 && 0<=Arg_4 && 0<=Arg_1+Arg_4 && Arg_3<=Arg_2 && Arg_3<=Arg_1 && Arg_2<=Arg_3 && Arg_2<=Arg_1 && 0<=Arg_1
f10(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> f18(Arg_0,Arg_1,Arg_2,Arg_2,0,Arg_5,Arg_6,Arg_7) :|: Arg_2<=Arg_1 && 0<=Arg_1

G f0 f0 f10 f10 f0->f10 t₀ ∈ g₀ η (Arg_0) = I η (Arg_1) = 0 f10->f10 t₁ ∈ g₁ η (Arg_1) = Arg_1+1 τ = Arg_1+1<=Arg_2 f18 f18 f10->f18 t₉ ∈ g₇ η (Arg_3) = Arg_2 η (Arg_4) = 0 τ = Arg_2<=Arg_1 f22 f22 f18->f22 t₂ ∈ g₂ η (Arg_5) = Arg_4 η (Arg_6) = Arg_4+1 τ = 2+Arg_4<=Arg_3 f34 f34 f18->f34 t₈ ∈ g₆ η (Arg_4) = 0 τ = Arg_3<=Arg_4+1 f22->f18 t₇ ∈ g₅ η (Arg_4) = Arg_4+1 η (Arg_7) = I τ = Arg_3<=Arg_6 f22->f22 t₃ ∈ g₃ p = 1/2 η (Arg_6) = Arg_6+1 τ = Arg_6+1<=Arg_3 f22->f22 t₄ ∈ g₃ p = 1/2 τ = Arg_6+1<=Arg_3 f22->f22 t₅ ∈ g₄ p = 1/2 η (Arg_5) = Arg_6 η (Arg_6) = Arg_6+1 τ = Arg_6+1<=Arg_3 f22->f22 t₆ ∈ g₄ p = 1/2 τ = Arg_6+1<=Arg_3

Timebounds:

Overall timebound:inf {Infinity}
0,0: f0->f10: 1 {O(1)}
1,1: f10->f10: max([0, Arg_2]) {O(n)}
9,7: f10->f18: 1 {O(1)}
2,2: f18->f22: max([1, 1+Arg_2]) {O(n)}
8,6: f18->f34: 1 {O(1)}
3,3: f22->f22: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2]) {O(n^2)}
4,3: f22->f22: inf {Infinity}
5,4: f22->f22: max([0, Arg_2])*max([1, 1+Arg_2]) {O(n^2)}
6,4: f22->f22: inf {Infinity}
7,5: f22->f18: max([0, Arg_2]) {O(n)}

Expected Timebounds:

Overall expected timebound: (1+Arg_2)*(2*(1+Arg_2)+2*Arg_2)+3*Arg_2+4+4*(1+Arg_2)*Arg_2 {O(n^2)}
0: f0->[1:f10]: 1 {O(1)}
1: f10->[1:f10]: Arg_2 {O(n)}
2: f18->[1:f22]: 1+Arg_2 {O(n)}
3: f22->[1/2:f22; 1/2:f22]: (1+Arg_2)*(2*(1+Arg_2)+2*Arg_2) {O(n^2)}
4: f22->[1/2:f22; 1/2:f22]: 4*(1+Arg_2)*Arg_2 {O(n^2)}
5: f22->[1:f18]: Arg_2 {O(n)}
6: f18->[1:f34]: 1 {O(1)}
7: f10->[1:f18]: 1 {O(1)}

Costbounds:

Overall costbound: inf {Infinity}
0,0: f0->f10: inf {Infinity}
1,1: f10->f10: inf {Infinity}
9,7: f10->f18: inf {Infinity}
2,2: f18->f22: inf {Infinity}
8,6: f18->f34: inf {Infinity}
3,3: f22->f22: inf {Infinity}
4,3: f22->f22: inf {Infinity}
5,4: f22->f22: inf {Infinity}
6,4: f22->f22: inf {Infinity}
7,5: f22->f18: inf {Infinity}

Expected Costbounds:

Overall expected costbound: (1+Arg_2)*(2*(1+Arg_2)+2*Arg_2)+3*Arg_2+4+4*(1+Arg_2)*Arg_2 {O(n^2)}
0: f0->[1:f10]: 1 {O(1)}
1: f10->[1:f10]: Arg_2 {O(n)}
2: f18->[1:f22]: 1+Arg_2 {O(n)}
3: f22->[1/2:f22; 1/2:f22]: (1+Arg_2)*(2*(1+Arg_2)+2*Arg_2) {O(n^2)}
4: f22->[1/2:f22; 1/2:f22]: 4*(1+Arg_2)*Arg_2 {O(n^2)}
5: f22->[1:f18]: Arg_2 {O(n)}
6: f18->[1:f34]: 1 {O(1)}
7: f10->[1:f18]: 1 {O(1)}

Sizebounds:

0,0: f0->f10, Arg_1: 0 {O(1)}
0,0: f0->f10, Arg_2: Arg_2 {O(n)}
0,0: f0->f10, Arg_3: Arg_3 {O(n)}
0,0: f0->f10, Arg_4: Arg_4 {O(n)}
0,0: f0->f10, Arg_5: Arg_5 {O(n)}
0,0: f0->f10, Arg_6: Arg_6 {O(n)}
0,0: f0->f10, Arg_7: Arg_7 {O(n)}
1,1: f10->f10, Arg_1: max([0, Arg_2]) {O(n)}
1,1: f10->f10, Arg_2: Arg_2 {O(n)}
1,1: f10->f10, Arg_3: Arg_3 {O(n)}
1,1: f10->f10, Arg_4: Arg_4 {O(n)}
1,1: f10->f10, Arg_5: Arg_5 {O(n)}
1,1: f10->f10, Arg_6: Arg_6 {O(n)}
1,1: f10->f10, Arg_7: Arg_7 {O(n)}
9,7: f10->f18, Arg_1: max([0, Arg_2]) {O(n)}
9,7: f10->f18, Arg_2: Arg_2 {O(n)}
9,7: f10->f18, Arg_3: Arg_2 {O(n)}
9,7: f10->f18, Arg_4: 0 {O(1)}
9,7: f10->f18, Arg_5: Arg_5 {O(n)}
9,7: f10->f18, Arg_6: Arg_6 {O(n)}
9,7: f10->f18, Arg_7: Arg_7 {O(n)}
2,2: f18->f22, Arg_1: max([0, Arg_2]) {O(n)}
2,2: f18->f22, Arg_2: Arg_2 {O(n)}
2,2: f18->f22, Arg_3: Arg_2 {O(n)}
2,2: f18->f22, Arg_4: max([0, Arg_2]) {O(n)}
2,2: f18->f22, Arg_5: max([0, Arg_2]) {O(n)}
2,2: f18->f22, Arg_6: max([1, 1+Arg_2]) {O(n)}
8,6: f18->f34, Arg_1: max([0, Arg_2]) {O(n)}
8,6: f18->f34, Arg_2: Arg_2 {O(n)}
8,6: f18->f34, Arg_3: Arg_2 {O(n)}
8,6: f18->f34, Arg_4: 0 {O(1)}
8,6: f18->f34, Arg_5: max([Arg_5, max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2])]) {O(n^2)}
8,6: f18->f34, Arg_6: max([Arg_6, max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2])]) {O(n^2)}
3,3: f22->f22, Arg_1: max([0, Arg_2]) {O(n)}
3,3: f22->f22, Arg_2: Arg_2 {O(n)}
3,3: f22->f22, Arg_3: Arg_2 {O(n)}
3,3: f22->f22, Arg_4: max([0, Arg_2]) {O(n)}
3,3: f22->f22, Arg_5: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
3,3: f22->f22, Arg_6: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
4,3: f22->f22, Arg_1: max([0, Arg_2]) {O(n)}
4,3: f22->f22, Arg_2: Arg_2 {O(n)}
4,3: f22->f22, Arg_3: Arg_2 {O(n)}
4,3: f22->f22, Arg_4: max([0, Arg_2]) {O(n)}
4,3: f22->f22, Arg_5: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
4,3: f22->f22, Arg_6: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
5,4: f22->f22, Arg_1: max([0, Arg_2]) {O(n)}
5,4: f22->f22, Arg_2: Arg_2 {O(n)}
5,4: f22->f22, Arg_3: Arg_2 {O(n)}
5,4: f22->f22, Arg_4: max([0, Arg_2]) {O(n)}
5,4: f22->f22, Arg_5: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
5,4: f22->f22, Arg_6: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
6,4: f22->f22, Arg_1: max([0, Arg_2]) {O(n)}
6,4: f22->f22, Arg_2: Arg_2 {O(n)}
6,4: f22->f22, Arg_3: Arg_2 {O(n)}
6,4: f22->f22, Arg_4: max([0, Arg_2]) {O(n)}
6,4: f22->f22, Arg_5: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
6,4: f22->f22, Arg_6: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
7,5: f22->f18, Arg_1: max([0, Arg_2]) {O(n)}
7,5: f22->f18, Arg_2: Arg_2 {O(n)}
7,5: f22->f18, Arg_3: Arg_2 {O(n)}
7,5: f22->f18, Arg_4: max([0, Arg_2]) {O(n)}
7,5: f22->f18, Arg_5: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}
7,5: f22->f18, Arg_6: max([(-1)+max([0, Arg_2]), 0])*max([1, 1+Arg_2])+max([0, Arg_2])*max([1, 1+Arg_2])+max([1, 1+Arg_2]) {O(n^2)}

ExpSizeBounds:

(0: f0->[1:f10], f10), I: I {O(n)}
(0: f0->[1:f10], f10), Arg_1: 0 {O(1)}
(0: f0->[1:f10], f10), Arg_2: Arg_2 {O(n)}
(0: f0->[1:f10], f10), Arg_3: Arg_3 {O(n)}
(0: f0->[1:f10], f10), Arg_4: Arg_4 {O(n)}
(0: f0->[1:f10], f10), Arg_5: Arg_5 {O(n)}
(0: f0->[1:f10], f10), Arg_6: Arg_6 {O(n)}
(0: f0->[1:f10], f10), Arg_7: Arg_7 {O(n)}
(1: f10->[1:f10], f10), I: I {O(n)}
(1: f10->[1:f10], f10), Arg_1: Arg_2 {O(n)}
(1: f10->[1:f10], f10), Arg_2: Arg_2 {O(n)}
(1: f10->[1:f10], f10), Arg_3: Arg_3 {O(n)}
(1: f10->[1:f10], f10), Arg_4: Arg_4 {O(n)}
(1: f10->[1:f10], f10), Arg_5: Arg_5 {O(n)}
(1: f10->[1:f10], f10), Arg_6: Arg_6 {O(n)}
(1: f10->[1:f10], f10), Arg_7: Arg_7 {O(n)}
(2: f18->[1:f22], f22), I: 2*I {O(n)}
(2: f18->[1:f22], f22), Arg_1: Arg_2 {O(n)}
(2: f18->[1:f22], f22), Arg_2: Arg_2 {O(n)}
(2: f18->[1:f22], f22), Arg_3: Arg_2 {O(n)}
(2: f18->[1:f22], f22), Arg_4: Arg_2 {O(n)}
(2: f18->[1:f22], f22), Arg_5: Arg_2 {O(n)}
(2: f18->[1:f22], f22), Arg_6: 1+Arg_2 {O(n)}
(3: f22->[1/2:f22; 1/2:f22], f22), I: 2*I {O(n)}
(3: f22->[1/2:f22; 1/2:f22], f22), Arg_1: Arg_2 {O(n)}
(3: f22->[1/2:f22; 1/2:f22], f22), Arg_2: Arg_2 {O(n)}
(3: f22->[1/2:f22; 1/2:f22], f22), Arg_3: Arg_2 {O(n)}
(3: f22->[1/2:f22; 1/2:f22], f22), Arg_4: Arg_2 {O(n)}
(3: f22->[1/2:f22; 1/2:f22], f22), Arg_5: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2 {O(n^2)}
(3: f22->[1/2:f22; 1/2:f22], f22), Arg_6: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2 {O(n^2)}
(4: f22->[1/2:f22; 1/2:f22], f22), I: 2*I {O(n)}
(4: f22->[1/2:f22; 1/2:f22], f22), Arg_1: Arg_2 {O(n)}
(4: f22->[1/2:f22; 1/2:f22], f22), Arg_2: Arg_2 {O(n)}
(4: f22->[1/2:f22; 1/2:f22], f22), Arg_3: Arg_2 {O(n)}
(4: f22->[1/2:f22; 1/2:f22], f22), Arg_4: Arg_2 {O(n)}
(4: f22->[1/2:f22; 1/2:f22], f22), Arg_5: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2 {O(n^2)}
(4: f22->[1/2:f22; 1/2:f22], f22), Arg_6: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2 {O(n^2)}
(5: f22->[1:f18], f18), I: 2*I {O(n)}
(5: f22->[1:f18], f18), Arg_1: Arg_2 {O(n)}
(5: f22->[1:f18], f18), Arg_2: Arg_2 {O(n)}
(5: f22->[1:f18], f18), Arg_3: Arg_2 {O(n)}
(5: f22->[1:f18], f18), Arg_4: Arg_2 {O(n)}
(5: f22->[1:f18], f18), Arg_5: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2 {O(n^2)}
(5: f22->[1:f18], f18), Arg_6: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2 {O(n^2)}
(6: f18->[1:f34], f34), I: 4*I {O(n)}
(6: f18->[1:f34], f34), Arg_1: Arg_2 {O(n)}
(6: f18->[1:f34], f34), Arg_2: Arg_2 {O(n)}
(6: f18->[1:f34], f34), Arg_3: Arg_2 {O(n)}
(6: f18->[1:f34], f34), Arg_4: 0 {O(1)}
(6: f18->[1:f34], f34), Arg_5: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2+Arg_5 {O(n^2)}
(6: f18->[1:f34], f34), Arg_6: (1+Arg_2)*(1+Arg_2)+(1+Arg_2)*Arg_2+1+Arg_2+Arg_6 {O(n^2)}
(7: f10->[1:f18], f18), I: 2*I {O(n)}
(7: f10->[1:f18], f18), Arg_1: Arg_2 {O(n)}
(7: f10->[1:f18], f18), Arg_2: Arg_2 {O(n)}
(7: f10->[1:f18], f18), Arg_3: Arg_2 {O(n)}
(7: f10->[1:f18], f18), Arg_4: 0 {O(1)}
(7: f10->[1:f18], f18), Arg_5: Arg_5 {O(n)}
(7: f10->[1:f18], f18), Arg_6: Arg_6 {O(n)}
(7: f10->[1:f18], f18), Arg_7: Arg_7 {O(n)}