0.06/0.41 WORST_CASE(?,O(n^1)) 0.06/0.41 0.06/0.41 Preprocessing Cost Relations 0.06/0.41 ===================================== 0.06/0.41 0.06/0.41 #### Computed strongly connected components 0.06/0.41 0. recursive : [eval_knuth_morris_pratt_0/11,eval_knuth_morris_pratt_1/12,eval_knuth_morris_pratt_2/12,eval_knuth_morris_pratt_3/13,eval_knuth_morris_pratt_bb2_in/11,eval_knuth_morris_pratt_bb3_in/11,eval_knuth_morris_pratt_bb4_in/12,eval_knuth_morris_pratt_bb5_in/13] 0.06/0.41 1. recursive : [eval_knuth_morris_pratt__critedge_in/6,eval_knuth_morris_pratt_bb1_in/5,eval_knuth_morris_pratt_bb2_in_loop_cont/7] 0.06/0.41 2. non_recursive : [eval_knuth_morris_pratt_stop/1] 0.06/0.41 3. non_recursive : [eval_knuth_morris_pratt_bb6_in/1] 0.06/0.41 4. non_recursive : [eval_knuth_morris_pratt_bb1_in_loop_cont/2] 0.06/0.41 5. non_recursive : [eval_knuth_morris_pratt_bb0_in/3] 0.06/0.41 6. non_recursive : [eval_knuth_morris_pratt_start/3] 0.06/0.41 0.06/0.41 #### Obtained direct recursion through partial evaluation 0.06/0.41 0. SCC is partially evaluated into eval_knuth_morris_pratt_bb2_in/11 0.06/0.41 1. SCC is partially evaluated into eval_knuth_morris_pratt_bb1_in/5 0.06/0.41 2. SCC is completely evaluated into other SCCs 0.06/0.41 3. SCC is completely evaluated into other SCCs 0.06/0.41 4. SCC is completely evaluated into other SCCs 0.06/0.41 5. SCC is partially evaluated into eval_knuth_morris_pratt_bb0_in/3 0.06/0.41 6. SCC is partially evaluated into eval_knuth_morris_pratt_start/3 0.06/0.41 0.06/0.41 Control-Flow Refinement of Cost Relations 0.06/0.41 ===================================== 0.06/0.41 0.06/0.41 ### Specialization of cost equations eval_knuth_morris_pratt_bb2_in/11 0.06/0.41 * CE 9 is refined into CE [11] 0.06/0.41 * CE 8 is refined into CE [12] 0.06/0.41 * CE 10 is refined into CE [13] 0.06/0.41 0.06/0.41 0.06/0.41 ### Cost equations --> "Loop" of eval_knuth_morris_pratt_bb2_in/11 0.06/0.41 * CEs [11] --> Loop 10 0.06/0.41 * CEs [12] --> Loop 11 0.06/0.41 * CEs [13] --> Loop 12 0.06/0.41 0.06/0.41 ### Ranking functions of CR eval_knuth_morris_pratt_bb2_in(V_n,V_m,V_j_0,V_i_0,V_j_1,B,C,D,E,F,G) 0.06/0.41 0.06/0.41 #### Partial ranking functions of CR eval_knuth_morris_pratt_bb2_in(V_n,V_m,V_j_0,V_i_0,V_j_1,B,C,D,E,F,G) 0.06/0.41 0.06/0.41 0.06/0.41 ### Specialization of cost equations eval_knuth_morris_pratt_bb1_in/5 0.06/0.41 * CE 5 is refined into CE [14,15] 0.06/0.41 * CE 6 is refined into CE [16] 0.06/0.41 * CE 7 is refined into CE [17] 0.06/0.41 * CE 4 is refined into CE [18,19] 0.06/0.41 * CE 3 is refined into CE [20,21] 0.06/0.41 0.06/0.41 0.06/0.41 ### Cost equations --> "Loop" of eval_knuth_morris_pratt_bb1_in/5 0.06/0.41 * CEs [19] --> Loop 13 0.06/0.41 * CEs [21] --> Loop 14 0.06/0.41 * CEs [18] --> Loop 15 0.06/0.41 * CEs [20] --> Loop 16 0.06/0.41 * CEs [17] --> Loop 17 0.06/0.41 * CEs [16] --> Loop 18 0.06/0.41 * CEs [14] --> Loop 19 0.06/0.41 * CEs [15] --> Loop 20 0.06/0.41 0.06/0.41 ### Ranking functions of CR eval_knuth_morris_pratt_bb1_in(V_n,V_m,V_j_0,V_i_0,B) 0.06/0.41 * RF of phase [13]: [V_m-V_i_0-1,V_m-V_j_0-1,V_n-V_i_0,V_n-V_j_0] 0.06/0.41 * RF of phase [14]: [V_n-V_i_0,V_n-V_j_0] 0.06/0.41 0.06/0.41 #### Partial ranking functions of CR eval_knuth_morris_pratt_bb1_in(V_n,V_m,V_j_0,V_i_0,B) 0.06/0.41 * Partial RF of phase [13]: 0.06/0.41 - RF of loop [13:1]: 0.06/0.41 V_m-V_i_0-1 0.06/0.41 V_m-V_j_0-1 0.06/0.41 V_n-V_i_0 0.06/0.41 V_n-V_j_0 0.06/0.41 * Partial RF of phase [14]: 0.06/0.41 - RF of loop [14:1]: 0.06/0.41 V_n-V_i_0 0.06/0.41 V_n-V_j_0 0.06/0.41 0.06/0.41 0.06/0.41 ### Specialization of cost equations eval_knuth_morris_pratt_bb0_in/3 0.06/0.41 * CE 2 is refined into CE [22,23,24,25,26,27,28,29] 0.06/0.41 0.06/0.41 0.06/0.41 ### Cost equations --> "Loop" of eval_knuth_morris_pratt_bb0_in/3 0.06/0.41 * CEs [25] --> Loop 21 0.06/0.41 * CEs [28] --> Loop 22 0.06/0.41 * CEs [23] --> Loop 23 0.06/0.41 * CEs [29] --> Loop 24 0.06/0.41 * CEs [27] --> Loop 25 0.06/0.41 * CEs [26] --> Loop 26 0.06/0.41 * CEs [24] --> Loop 27 0.06/0.41 * CEs [22] --> Loop 28 0.06/0.41 0.06/0.41 ### Ranking functions of CR eval_knuth_morris_pratt_bb0_in(V_n,V_m,B) 0.06/0.41 0.06/0.41 #### Partial ranking functions of CR eval_knuth_morris_pratt_bb0_in(V_n,V_m,B) 0.06/0.41 0.06/0.41 0.06/0.41 ### Specialization of cost equations eval_knuth_morris_pratt_start/3 0.06/0.41 * CE 1 is refined into CE [30,31,32,33,34,35,36,37] 0.06/0.41 0.06/0.41 0.06/0.41 ### Cost equations --> "Loop" of eval_knuth_morris_pratt_start/3 0.06/0.41 * CEs [37] --> Loop 29 0.06/0.41 * CEs [36] --> Loop 30 0.06/0.41 * CEs [35] --> Loop 31 0.06/0.41 * CEs [34] --> Loop 32 0.06/0.41 * CEs [33] --> Loop 33 0.06/0.41 * CEs [32] --> Loop 34 0.06/0.41 * CEs [31] --> Loop 35 0.06/0.41 * CEs [30] --> Loop 36 0.06/0.41 0.06/0.41 ### Ranking functions of CR eval_knuth_morris_pratt_start(V_n,V_m,B) 0.06/0.41 0.06/0.41 #### Partial ranking functions of CR eval_knuth_morris_pratt_start(V_n,V_m,B) 0.06/0.41 0.06/0.41 0.06/0.41 Computing Bounds 0.06/0.41 ===================================== 0.06/0.41 0.06/0.41 #### Cost of chains of eval_knuth_morris_pratt_bb2_in(V_n,V_m,V_j_0,V_i_0,V_j_1,B,C,D,E,F,G): 0.06/0.41 * Chain [12]: 0 0.06/0.41 with precondition: [B=2,D=V_m,V_j_1=V_j_0,V_n=C,V_j_1=E,V_i_0=F,V_j_1=G,0>=V_j_1+1,V_n>=V_i_0+1] 0.06/0.41 0.06/0.41 * Chain [11]: 0 0.06/0.41 with precondition: [B=2,D=V_m,V_j_1=V_j_0,V_n=C,V_j_1=E,V_i_0=F,V_j_1=G,V_j_1>=0,V_n>=V_i_0+1] 0.06/0.41 0.06/0.41 * Chain [10]: 0 0.06/0.41 with precondition: [B=3,V_j_1=V_j_0,V_j_1>=0,V_n>=V_i_0+1] 0.06/0.41 0.06/0.41 0.06/0.41 #### Cost of chains of eval_knuth_morris_pratt_bb1_in(V_n,V_m,V_j_0,V_i_0,B): 0.06/0.41 * Chain [[14],18]: 1*it(14)+0 0.06/0.41 Such that:it(14) =< V_n-V_j_0 0.06/0.41 0.06/0.41 with precondition: [B=3,V_i_0=V_j_0,V_i_0>=0,V_i_0>=V_m,V_n>=V_i_0+2] 0.06/0.41 0.06/0.41 * Chain [[14],17]: 1*it(14)+0 0.06/0.41 Such that:it(14) =< V_n-V_j_0 0.06/0.41 0.06/0.41 with precondition: [B=3,V_i_0=V_j_0,V_i_0>=0,V_i_0>=V_m,V_n>=V_i_0+1] 0.06/0.41 0.06/0.41 * Chain [[13],20]: 1*it(13)+0 0.06/0.41 Such that:it(13) =< V_m-V_i_0 0.06/0.41 0.06/0.41 with precondition: [B=3,V_i_0=V_j_0,V_i_0>=0,V_n>=V_m,V_m>=V_i_0+2] 0.06/0.41 0.06/0.41 * Chain [[13],18]: 1*it(13)+0 0.06/0.41 Such that:it(13) =< V_n-V_j_0 0.06/0.41 it(13) =< V_m-V_j_0 0.06/0.41 0.06/0.41 with precondition: [B=3,V_i_0=V_j_0,V_i_0>=0,V_n>=V_i_0+2,V_m>=V_i_0+2] 0.06/0.41 0.06/0.41 * Chain [[13],17]: 1*it(13)+0 0.06/0.41 Such that:it(13) =< V_n-V_j_0 0.06/0.41 0.06/0.41 with precondition: [B=3,V_i_0=V_j_0,V_i_0>=0,V_m>=V_n+1,V_n>=V_i_0+1] 0.06/0.41 0.06/0.41 * Chain [20]: 0 0.06/0.41 with precondition: [B=3,V_j_0+1=V_m,V_j_0=V_i_0,V_j_0>=0,V_n>=V_j_0+1] 0.06/0.41 0.06/0.41 * Chain [18]: 0 0.06/0.41 with precondition: [B=3,V_j_0=V_i_0,V_j_0>=0,V_n>=V_j_0+1] 0.06/0.41 0.06/0.41 * Chain [17]: 0 0.06/0.41 with precondition: [B=3,V_i_0=V_j_0,V_i_0>=0,V_i_0>=V_n] 0.06/0.41 0.06/0.41 0.06/0.41 #### Cost of chains of eval_knuth_morris_pratt_bb0_in(V_n,V_m,B): 0.06/0.41 * Chain [28]: 0 0.06/0.41 with precondition: [V_m=1,V_n>=1] 0.06/0.41 0.06/0.41 * Chain [27]: 0 0.06/0.41 with precondition: [0>=V_n] 0.06/0.41 0.06/0.41 * Chain [26]: 1*s(1)+0 0.06/0.41 Such that:s(1) =< V_n 0.06/0.41 0.06/0.41 with precondition: [0>=V_m,V_n>=1] 0.06/0.41 0.06/0.41 * Chain [25]: 1*s(2)+0 0.06/0.41 Such that:s(2) =< V_n 0.06/0.41 0.06/0.41 with precondition: [0>=V_m,V_n>=2] 0.06/0.41 0.06/0.41 * Chain [24]: 0 0.06/0.41 with precondition: [V_n>=1] 0.06/0.41 0.06/0.41 * Chain [23]: 1*s(3)+0 0.06/0.41 Such that:s(3) =< V_n 0.06/0.41 0.06/0.41 with precondition: [V_n>=1,V_m>=V_n+1] 0.06/0.41 0.06/0.41 * Chain [22]: 1*s(4)+0 0.06/0.41 Such that:s(4) =< V_n 0.06/0.41 s(4) =< V_m 0.06/0.41 0.06/0.41 with precondition: [V_n>=2,V_m>=2] 0.06/0.41 0.06/0.41 * Chain [21]: 1*s(5)+0 0.06/0.41 Such that:s(5) =< V_m 0.06/0.41 0.06/0.41 with precondition: [V_m>=2,V_n>=V_m] 0.06/0.41 0.06/0.41 0.06/0.41 #### Cost of chains of eval_knuth_morris_pratt_start(V_n,V_m,B): 0.06/0.41 * Chain [36]: 0 0.06/0.41 with precondition: [V_m=1,V_n>=1] 0.06/0.41 0.06/0.41 * Chain [35]: 0 0.06/0.41 with precondition: [0>=V_n] 0.06/0.41 0.06/0.41 * Chain [34]: 1*s(6)+0 0.06/0.41 Such that:s(6) =< V_n 0.06/0.41 0.06/0.41 with precondition: [0>=V_m,V_n>=1] 0.06/0.41 0.06/0.41 * Chain [33]: 1*s(7)+0 0.06/0.41 Such that:s(7) =< V_n 0.06/0.41 0.06/0.41 with precondition: [0>=V_m,V_n>=2] 0.06/0.41 0.06/0.41 * Chain [32]: 0 0.06/0.41 with precondition: [V_n>=1] 0.06/0.41 0.06/0.41 * Chain [31]: 1*s(8)+0 0.06/0.41 Such that:s(8) =< V_n 0.06/0.41 0.06/0.41 with precondition: [V_n>=1,V_m>=V_n+1] 0.06/0.41 0.06/0.41 * Chain [30]: 1*s(9)+0 0.06/0.41 Such that:s(9) =< V_n 0.06/0.41 s(9) =< V_m 0.06/0.41 0.06/0.41 with precondition: [V_n>=2,V_m>=2] 0.06/0.41 0.06/0.41 * Chain [29]: 1*s(10)+0 0.06/0.41 Such that:s(10) =< V_m 0.06/0.41 0.06/0.41 with precondition: [V_m>=2,V_n>=V_m] 0.06/0.41 0.06/0.41 0.06/0.41 Closed-form bounds of eval_knuth_morris_pratt_start(V_n,V_m,B): 0.06/0.41 ------------------------------------- 0.06/0.41 * Chain [36] with precondition: [V_m=1,V_n>=1] 0.06/0.41 - Upper bound: 0 0.06/0.41 - Complexity: constant 0.06/0.41 * Chain [35] with precondition: [0>=V_n] 0.06/0.41 - Upper bound: 0 0.06/0.41 - Complexity: constant 0.06/0.41 * Chain [34] with precondition: [0>=V_m,V_n>=1] 0.06/0.41 - Upper bound: V_n 0.06/0.41 - Complexity: n 0.06/0.41 * Chain [33] with precondition: [0>=V_m,V_n>=2] 0.06/0.41 - Upper bound: V_n 0.06/0.41 - Complexity: n 0.06/0.41 * Chain [32] with precondition: [V_n>=1] 0.06/0.41 - Upper bound: 0 0.06/0.41 - Complexity: constant 0.06/0.41 * Chain [31] with precondition: [V_n>=1,V_m>=V_n+1] 0.06/0.41 - Upper bound: V_n 0.06/0.41 - Complexity: n 0.06/0.41 * Chain [30] with precondition: [V_n>=2,V_m>=2] 0.06/0.41 - Upper bound: V_n 0.06/0.41 - Complexity: n 0.06/0.41 * Chain [29] with precondition: [V_m>=2,V_n>=V_m] 0.06/0.41 - Upper bound: V_m 0.06/0.41 - Complexity: n 0.06/0.41 0.06/0.41 ### Maximum cost of eval_knuth_morris_pratt_start(V_n,V_m,B): max([nat(V_n),nat(V_m)]) 0.06/0.41 Asymptotic class: n 0.06/0.41 * Total analysis performed in 315 ms. 0.06/0.41 0.06/0.51 EOF