1.58/1.60 WORST_CASE(?,O(n^2)) 1.58/1.60 1.58/1.60 Preprocessing Cost Relations 1.58/1.60 ===================================== 1.58/1.60 1.58/1.60 #### Computed strongly connected components 1.58/1.60 0. recursive : [eval_xnu_15/9,eval_xnu_16/9,eval_xnu_bb3_in/9,eval_xnu_bb4_in/9] 1.58/1.60 1. recursive : [eval_xnu_10/20,eval_xnu_11/20,eval_xnu_12/20,eval_xnu_13/20,eval_xnu_bb1_in/20,eval_xnu_bb2_in/20,eval_xnu_bb3_in_loop_cont/21] 1.58/1.60 2. non_recursive : [eval_xnu_stop/11] 1.58/1.60 3. non_recursive : [eval_xnu_bb5_in/11] 1.58/1.60 4. non_recursive : [exit_location/1] 1.58/1.60 5. non_recursive : [eval_xnu_bb1_in_loop_cont/12] 1.58/1.60 6. non_recursive : [eval_xnu_8/11] 1.58/1.60 7. non_recursive : [eval_xnu_7/11] 1.58/1.60 8. non_recursive : [eval_xnu_6/11] 1.58/1.60 9. non_recursive : [eval_xnu_5/11] 1.58/1.60 10. non_recursive : [eval_xnu_4/11] 1.58/1.60 11. non_recursive : [eval_xnu_3/11] 1.58/1.60 12. non_recursive : [eval_xnu_2/11] 1.58/1.60 13. non_recursive : [eval_xnu_1/11] 1.58/1.60 14. non_recursive : [eval_xnu_0/11] 1.58/1.60 15. non_recursive : [eval_xnu_bb0_in/11] 1.58/1.60 16. non_recursive : [eval_xnu_start/11] 1.58/1.60 1.58/1.60 #### Obtained direct recursion through partial evaluation 1.58/1.60 0. SCC is partially evaluated into eval_xnu_bb3_in/9 1.58/1.60 1. SCC is partially evaluated into eval_xnu_bb1_in/20 1.58/1.60 2. SCC is completely evaluated into other SCCs 1.58/1.60 3. SCC is completely evaluated into other SCCs 1.58/1.60 4. SCC is completely evaluated into other SCCs 1.58/1.60 5. SCC is partially evaluated into eval_xnu_bb1_in_loop_cont/12 1.58/1.60 6. SCC is partially evaluated into eval_xnu_8/11 1.58/1.60 7. SCC is completely evaluated into other SCCs 1.58/1.60 8. SCC is completely evaluated into other SCCs 1.58/1.60 9. SCC is completely evaluated into other SCCs 1.58/1.60 10. SCC is completely evaluated into other SCCs 1.58/1.60 11. SCC is completely evaluated into other SCCs 1.58/1.60 12. SCC is completely evaluated into other SCCs 1.58/1.60 13. SCC is completely evaluated into other SCCs 1.58/1.60 14. SCC is completely evaluated into other SCCs 1.58/1.60 15. SCC is completely evaluated into other SCCs 1.58/1.60 16. SCC is partially evaluated into eval_xnu_start/11 1.58/1.60 1.58/1.60 Control-Flow Refinement of Cost Relations 1.58/1.60 ===================================== 1.58/1.60 1.58/1.60 ### Specialization of cost equations eval_xnu_bb3_in/9 1.58/1.60 * CE 15 is refined into CE [16] 1.58/1.60 * CE 14 is refined into CE [17] 1.58/1.60 * CE 13 is refined into CE [18] 1.58/1.60 1.58/1.60 1.58/1.60 ### Cost equations --> "Loop" of eval_xnu_bb3_in/9 1.58/1.60 * CEs [18] --> Loop 15 1.58/1.60 * CEs [16] --> Loop 16 1.58/1.60 * CEs [17] --> Loop 17 1.58/1.60 1.58/1.60 ### Ranking functions of CR eval_xnu_bb3_in(V__end_0,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,B,C,D) 1.58/1.60 * RF of phase [15]: [V__end_0-V_k_0,V_i_0-V_k_0+1] 1.58/1.60 1.58/1.60 #### Partial ranking functions of CR eval_xnu_bb3_in(V__end_0,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,B,C,D) 1.58/1.60 * Partial RF of phase [15]: 1.58/1.60 - RF of loop [15:1]: 1.58/1.60 V__end_0-V_k_0 1.58/1.60 V_i_0-V_k_0+1 1.58/1.60 1.58/1.60 1.58/1.60 ### Specialization of cost equations eval_xnu_bb1_in/20 1.58/1.60 * CE 9 is refined into CE [19] 1.58/1.60 * CE 7 is refined into CE [20,21] 1.58/1.60 * CE 8 is refined into CE [22,23] 1.58/1.60 * CE 10 is refined into CE [24] 1.58/1.60 * CE 6 is refined into CE [25,26] 1.58/1.60 * CE 4 is refined into CE [27] 1.58/1.60 * CE 5 is refined into CE [28] 1.58/1.60 * CE 3 is refined into CE [29] 1.58/1.60 1.58/1.60 1.58/1.60 ### Cost equations --> "Loop" of eval_xnu_bb1_in/20 1.58/1.60 * CEs [26] --> Loop 18 1.58/1.60 * CEs [27] --> Loop 19 1.58/1.60 * CEs [28] --> Loop 20 1.58/1.60 * CEs [29] --> Loop 21 1.58/1.60 * CEs [25] --> Loop 22 1.58/1.60 * CEs [19] --> Loop 23 1.58/1.60 * CEs [23] --> Loop 24 1.58/1.60 * CEs [20,21,22] --> Loop 25 1.58/1.60 * CEs [24] --> Loop 26 1.58/1.60 1.58/1.60 ### Ranking functions of CR eval_xnu_bb1_in(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B,C,D,E,F,G,H,I,J,K) 1.58/1.60 * RF of phase [18,19,20,21,22]: [-V_i_0+V_len] 1.58/1.60 1.58/1.60 #### Partial ranking functions of CR eval_xnu_bb1_in(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B,C,D,E,F,G,H,I,J,K) 1.58/1.60 * Partial RF of phase [18,19,20,21,22]: 1.58/1.60 - RF of loop [18:1]: 1.58/1.60 -V_beg_0+V_end_0 depends on loops [21:1] 1.58/1.60 -V_beg_0+V_i_0 depends on loops [19:1,21:1] 1.58/1.60 -V_beg_0/2+V_len/2-1/2 1.58/1.60 - RF of loop [18:1,19:1,20:1,21:1,22:1]: 1.58/1.60 -V_i_0+V_len 1.58/1.60 - RF of loop [18:1,20:1,21:1,22:1]: 1.58/1.60 -V_end_0+V_len 1.58/1.60 - RF of loop [20:1,22:1]: 1.58/1.60 -V_beg_0+V_len 1.58/1.60 1.58/1.60 1.58/1.60 ### Specialization of cost equations eval_xnu_bb1_in_loop_cont/12 1.58/1.60 * CE 11 is refined into CE [30] 1.58/1.60 * CE 12 is refined into CE [31] 1.58/1.60 1.58/1.60 1.58/1.60 ### Cost equations --> "Loop" of eval_xnu_bb1_in_loop_cont/12 1.58/1.60 * CEs [30] --> Loop 27 1.58/1.60 * CEs [31] --> Loop 28 1.58/1.60 1.58/1.60 ### Ranking functions of CR eval_xnu_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) 1.58/1.60 1.58/1.60 #### Partial ranking functions of CR eval_xnu_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) 1.58/1.60 1.58/1.60 1.58/1.60 ### Specialization of cost equations eval_xnu_8/11 1.58/1.60 * CE 2 is refined into CE [32,33,34,35,36] 1.58/1.60 1.58/1.60 1.58/1.60 ### Cost equations --> "Loop" of eval_xnu_8/11 1.58/1.60 * CEs [34] --> Loop 29 1.58/1.60 * CEs [33,36] --> Loop 30 1.58/1.60 * CEs [35] --> Loop 31 1.58/1.60 * CEs [32] --> Loop 32 1.58/1.60 1.58/1.60 ### Ranking functions of CR eval_xnu_8(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B) 1.58/1.60 1.58/1.60 #### Partial ranking functions of CR eval_xnu_8(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B) 1.58/1.60 1.58/1.60 1.58/1.60 ### Specialization of cost equations eval_xnu_start/11 1.58/1.60 * CE 1 is refined into CE [37,38,39,40] 1.58/1.60 1.58/1.60 1.58/1.60 ### Cost equations --> "Loop" of eval_xnu_start/11 1.58/1.60 * CEs [40] --> Loop 33 1.58/1.60 * CEs [39] --> Loop 34 1.58/1.60 * CEs [38] --> Loop 35 1.58/1.60 * CEs [37] --> Loop 36 1.58/1.60 1.58/1.60 ### Ranking functions of CR eval_xnu_start(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B) 1.58/1.60 1.58/1.60 #### Partial ranking functions of CR eval_xnu_start(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B) 1.58/1.60 1.58/1.60 1.58/1.60 Computing Bounds 1.58/1.60 ===================================== 1.58/1.60 1.58/1.60 #### Cost of chains of eval_xnu_bb3_in(V__end_0,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,B,C,D): 1.58/1.60 * Chain [[15],17]: 1*it(15)+0 1.58/1.60 Such that:it(15) =< -V_k_0+C 1.58/1.60 1.58/1.60 with precondition: [B=2,V__end_0=C,V__end_0=D,V_beg_0>=0,V_i_0+1>=V__end_0,V_end_0>=V_beg_0,V_k_0>=V_beg_0,V__end_0>=V_end_0,V_i_0>=V_end_0,V__end_0>=V_k_0+1] 1.58/1.60 1.58/1.60 * Chain [[15],16]: 1*it(15)+0 1.58/1.60 Such that:it(15) =< V__end_0-V_k_0 1.58/1.60 1.58/1.60 with precondition: [B=3,V_beg_0>=0,V_i_0+1>=V__end_0,V_end_0>=V_beg_0,V_k_0>=V_beg_0,V__end_0>=V_end_0,V_i_0>=V_end_0,V__end_0>=V_k_0+1] 1.58/1.60 1.58/1.60 * Chain [17]: 0 1.58/1.60 with precondition: [B=2,V_k_0=V__end_0,C=V_7,V_k_0=D,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0,V_k_0>=V_end_0,V_i_0+1>=V_k_0] 1.58/1.60 1.58/1.60 * Chain [16]: 0 1.58/1.60 with precondition: [B=3,V_beg_0>=0,V_i_0+1>=V__end_0,V_end_0>=V_beg_0,V_k_0>=V_beg_0,V__end_0>=V_end_0,V_i_0>=V_end_0,V__end_0>=V_k_0] 1.58/1.60 1.58/1.60 1.58/1.60 #### Cost of chains of eval_xnu_bb1_in(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B,C,D,E,F,G,H,I,J,K): 1.58/1.60 * Chain [[18,19,20,21,22],26]: 1*it(18)+1*it(19)+2*it(20)+1*it(21)+1*s(5)+1*s(6)+0 1.58/1.60 Such that:it(18) =< -V_beg_0/2+V_len/2 1.58/1.60 aux(15) =< V_end_0 1.58/1.60 aux(6) =< V_i_0 1.58/1.60 aux(22) =< V_len 1.58/1.60 aux(23) =< -V_beg_0+V_end_0 1.58/1.60 aux(24) =< -V_beg_0+V_i_0 1.58/1.60 aux(25) =< -V_beg_0+V_len 1.58/1.60 aux(26) =< -V_end_0+V_len 1.58/1.60 aux(27) =< -V_i_0+V_len 1.58/1.60 aux(15) =< aux(23) 1.58/1.60 aux(6) =< aux(24) 1.58/1.60 aux(9) =< aux(25) 1.58/1.60 it(20) =< aux(25) 1.58/1.60 s(6) =< aux(25) 1.58/1.60 it(18) =< aux(26) 1.58/1.60 it(20) =< aux(26) 1.58/1.60 it(21) =< aux(26) 1.58/1.60 it(18) =< aux(27) 1.58/1.60 it(19) =< aux(27) 1.58/1.60 it(20) =< aux(27) 1.58/1.60 it(21) =< aux(27) 1.58/1.60 aux(9) =< aux(22) 1.58/1.60 aux(12) =< aux(22) 1.58/1.60 aux(11) =< it(21)*aux(22) 1.58/1.60 aux(1) =< it(21)*aux(22) 1.58/1.60 it(18) =< it(21)+it(19)+aux(6) 1.58/1.60 it(18) =< it(21)+it(19)+aux(24) 1.58/1.60 aux(13) =< it(21)*aux(12) 1.58/1.60 aux(1) =< it(21)*aux(12) 1.58/1.60 aux(4) =< aux(11) 1.58/1.60 aux(4) =< aux(13) 1.58/1.60 s(5) =< aux(1)+aux(23) 1.58/1.60 it(18) =< aux(1)+aux(23) 1.58/1.60 s(5) =< aux(4)+aux(15) 1.58/1.60 it(18) =< aux(4)+aux(15) 1.58/1.60 s(5) =< it(18)*aux(9) 1.58/1.60 1.58/1.60 with precondition: [B=3,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0,V_len>=V_i_0+1] 1.58/1.60 1.58/1.60 * Chain [[18,19,20,21,22],25]: 1*it(18)+1*it(19)+2*it(20)+1*it(21)+1*s(5)+2*s(6)+0 1.58/1.60 Such that:it(18) =< -V_beg_0/2+V_len/2 1.58/1.60 aux(15) =< V_end_0 1.58/1.60 aux(6) =< V_i_0 1.58/1.60 aux(22) =< V_len 1.58/1.60 aux(28) =< -V_beg_0+V_end_0 1.58/1.60 aux(29) =< -V_beg_0+V_i_0 1.58/1.60 aux(30) =< -V_beg_0+V_len 1.58/1.60 aux(31) =< -V_end_0+V_len 1.58/1.60 aux(32) =< -V_i_0+V_len 1.58/1.60 aux(15) =< aux(28) 1.58/1.60 aux(6) =< aux(29) 1.58/1.60 it(18) =< aux(30) 1.58/1.60 s(6) =< aux(30) 1.58/1.60 aux(9) =< aux(30) 1.58/1.60 it(20) =< aux(30) 1.58/1.60 it(18) =< aux(31) 1.58/1.60 it(20) =< aux(31) 1.58/1.60 it(21) =< aux(31) 1.58/1.60 it(18) =< aux(32) 1.58/1.60 it(19) =< aux(32) 1.58/1.60 it(20) =< aux(32) 1.58/1.60 it(21) =< aux(32) 1.58/1.60 aux(9) =< aux(22) 1.58/1.60 aux(12) =< aux(22) 1.58/1.60 aux(11) =< it(21)*aux(22) 1.58/1.60 aux(1) =< it(21)*aux(22) 1.58/1.60 it(18) =< it(21)+it(19)+aux(6) 1.58/1.60 it(18) =< it(21)+it(19)+aux(29) 1.58/1.60 aux(13) =< it(21)*aux(12) 1.58/1.60 aux(1) =< it(21)*aux(12) 1.58/1.60 aux(4) =< aux(11) 1.58/1.60 aux(4) =< aux(13) 1.58/1.60 s(5) =< aux(1)+aux(28) 1.58/1.60 it(18) =< aux(1)+aux(28) 1.58/1.60 s(5) =< aux(4)+aux(15) 1.58/1.60 it(18) =< aux(4)+aux(15) 1.58/1.60 s(5) =< it(18)*aux(9) 1.58/1.60 1.58/1.60 with precondition: [B=3,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0,V_len>=V_i_0+2] 1.58/1.60 1.58/1.60 * Chain [[18,19,20,21,22],24]: 1*it(18)+1*it(19)+2*it(20)+1*it(21)+1*s(5)+2*s(6)+0 1.58/1.60 Such that:it(18) =< -V_beg_0/2+V_len/2 1.58/1.60 aux(15) =< V_end_0 1.58/1.60 aux(6) =< V_i_0 1.58/1.60 aux(22) =< V_len 1.58/1.60 aux(33) =< -V_beg_0+V_end_0 1.58/1.60 aux(34) =< -V_beg_0+V_i_0 1.58/1.60 aux(35) =< -V_beg_0+V_len 1.58/1.60 aux(36) =< -V_end_0+V_len 1.58/1.60 aux(37) =< -V_i_0+V_len 1.58/1.60 aux(15) =< aux(33) 1.58/1.60 aux(6) =< aux(34) 1.58/1.60 it(18) =< aux(35) 1.58/1.60 s(6) =< aux(35) 1.58/1.60 aux(9) =< aux(35) 1.58/1.60 it(20) =< aux(35) 1.58/1.60 it(18) =< aux(36) 1.58/1.60 it(20) =< aux(36) 1.58/1.60 it(21) =< aux(36) 1.58/1.60 it(18) =< aux(37) 1.58/1.60 it(19) =< aux(37) 1.58/1.60 it(20) =< aux(37) 1.58/1.60 it(21) =< aux(37) 1.58/1.60 aux(9) =< aux(22) 1.58/1.60 aux(12) =< aux(22) 1.58/1.60 aux(11) =< it(21)*aux(22) 1.58/1.60 aux(1) =< it(21)*aux(22) 1.58/1.60 it(18) =< it(21)+it(19)+aux(6) 1.58/1.60 it(18) =< it(21)+it(19)+aux(34) 1.58/1.60 aux(13) =< it(21)*aux(12) 1.58/1.60 aux(1) =< it(21)*aux(12) 1.58/1.60 aux(4) =< aux(11) 1.58/1.60 aux(4) =< aux(13) 1.58/1.60 s(5) =< aux(1)+aux(33) 1.58/1.60 it(18) =< aux(1)+aux(33) 1.58/1.60 s(5) =< aux(4)+aux(15) 1.58/1.60 it(18) =< aux(4)+aux(15) 1.58/1.60 s(5) =< it(18)*aux(9) 1.58/1.60 1.58/1.60 with precondition: [B=3,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0,V_len>=V_i_0+2] 1.58/1.60 1.58/1.60 * Chain [[18,19,20,21,22],23]: 1*it(18)+1*it(19)+2*it(20)+1*it(21)+1*s(5)+1*s(6)+0 1.58/1.60 Such that:aux(14) =< -V_beg_0+V_end_0 1.58/1.60 aux(15) =< -V_beg_0+V_end_0+H-I 1.58/1.60 aux(3) =< -V_beg_0+V_i_0 1.58/1.60 aux(6) =< -V_beg_0+V_i_0+H-J 1.58/1.60 aux(17) =< -V_beg_0+H 1.58/1.60 aux(16) =< -V_beg_0+J 1.58/1.60 it(18) =< -V_beg_0/2+H/2 1.58/1.60 aux(19) =< -V_end_0+I 1.58/1.60 aux(18) =< -V_end_0+J 1.58/1.60 aux(15) =< V_end_0+H-I 1.58/1.60 aux(6) =< V_i_0-V_len+H 1.58/1.60 aux(22) =< J 1.58/1.60 aux(38) =< -V_i_0+J 1.58/1.60 aux(9) =< aux(16) 1.58/1.60 it(20) =< aux(16) 1.58/1.60 s(6) =< aux(16) 1.58/1.60 it(20) =< aux(17) 1.58/1.60 s(6) =< aux(17) 1.58/1.60 it(18) =< aux(18) 1.58/1.60 it(20) =< aux(18) 1.58/1.60 it(21) =< aux(18) 1.58/1.60 it(18) =< aux(19) 1.58/1.60 it(20) =< aux(19) 1.58/1.60 it(21) =< aux(19) 1.58/1.60 it(18) =< aux(38) 1.58/1.60 it(19) =< aux(38) 1.58/1.61 it(20) =< aux(38) 1.58/1.61 it(21) =< aux(38) 1.58/1.61 aux(9) =< aux(22) 1.58/1.61 aux(12) =< aux(22) 1.58/1.61 aux(11) =< it(21)*aux(22) 1.58/1.61 aux(1) =< it(21)*aux(22) 1.58/1.61 it(18) =< it(21)+it(19)+aux(6) 1.58/1.61 it(18) =< it(21)+it(19)+aux(3) 1.58/1.61 aux(13) =< it(21)*aux(12) 1.58/1.61 aux(1) =< it(21)*aux(12) 1.58/1.61 aux(4) =< aux(11) 1.58/1.61 aux(4) =< aux(13) 1.58/1.61 s(5) =< aux(1)+aux(14) 1.58/1.61 it(18) =< aux(1)+aux(14) 1.58/1.61 s(5) =< aux(4)+aux(15) 1.58/1.61 it(18) =< aux(4)+aux(15) 1.58/1.61 s(5) =< it(18)*aux(9) 1.58/1.61 1.58/1.61 with precondition: [B=4,V_len=D,V_len=J,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0,C>=V_end_0,V_len>=V_i_0+1,I>=C,I>=H,V_len>=I,C+H>=V_beg_0+I] 1.58/1.61 1.58/1.61 * Chain [26]: 0 1.58/1.61 with precondition: [B=3,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0] 1.58/1.61 1.58/1.61 * Chain [25]: 1*s(7)+0 1.58/1.61 Such that:s(7) =< -V_beg_0+V_i_0+1 1.58/1.61 1.58/1.61 with precondition: [B=3,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0,V_len>=V_i_0+1] 1.58/1.61 1.58/1.61 * Chain [23]: 0 1.58/1.61 with precondition: [B=4,C=V__end_0,D=V_1,E=V_2,F=V_4,G=V_7,K=V_k_0,V_beg_0=H,V_end_0=I,V_i_0=J,V_beg_0>=0,V_end_0>=V_beg_0,V_i_0>=V_end_0,V_i_0>=V_len] 1.58/1.61 1.58/1.61 1.58/1.61 #### Cost of chains of eval_xnu_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): 1.58/1.61 * Chain [28]: 0 1.58/1.61 with precondition: [A=3] 1.58/1.61 1.58/1.61 * Chain [27]: 0 1.58/1.61 with precondition: [A=4] 1.58/1.61 1.58/1.61 1.58/1.61 #### Cost of chains of eval_xnu_8(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B): 1.58/1.61 * Chain [32]: 0 1.58/1.61 with precondition: [] 1.58/1.61 1.58/1.61 * Chain [31]: 0 1.58/1.61 with precondition: [0>=V_len] 1.58/1.61 1.58/1.61 * Chain [30]: 1*s(72)+2*s(74)+10*s(81)+2*s(90)+0 1.58/1.61 Such that:s(72) =< 1 1.58/1.61 aux(52) =< V_len 1.58/1.61 aux(53) =< V_len/2 1.58/1.61 s(74) =< aux(53) 1.58/1.61 s(81) =< aux(52) 1.58/1.61 s(74) =< aux(52) 1.58/1.61 s(85) =< aux(52) 1.58/1.61 s(86) =< s(81)*aux(52) 1.58/1.61 s(87) =< s(81)*aux(52) 1.58/1.61 s(74) =< s(81)+s(81) 1.58/1.61 s(88) =< s(81)*s(85) 1.58/1.61 s(87) =< s(81)*s(85) 1.58/1.61 s(89) =< s(86) 1.58/1.61 s(89) =< s(88) 1.58/1.61 s(90) =< s(87) 1.58/1.61 s(74) =< s(87) 1.58/1.61 s(90) =< s(89) 1.58/1.61 s(74) =< s(89) 1.58/1.61 s(90) =< s(74)*aux(52) 1.58/1.61 1.58/1.61 with precondition: [V_len>=1] 1.58/1.61 1.58/1.61 * Chain [29]: 2*s(122)+12*s(125)+2*s(135)+0 1.58/1.61 Such that:s(116) =< V_len/2 1.58/1.61 aux(55) =< V_len 1.58/1.61 s(122) =< s(116) 1.58/1.61 s(122) =< aux(55) 1.58/1.61 s(125) =< aux(55) 1.58/1.61 s(130) =< aux(55) 1.58/1.61 s(131) =< s(125)*aux(55) 1.58/1.61 s(132) =< s(125)*aux(55) 1.58/1.61 s(122) =< s(125)+s(125) 1.58/1.61 s(133) =< s(125)*s(130) 1.58/1.61 s(132) =< s(125)*s(130) 1.58/1.61 s(134) =< s(131) 1.58/1.61 s(134) =< s(133) 1.58/1.61 s(135) =< s(132) 1.58/1.61 s(122) =< s(132) 1.58/1.61 s(135) =< s(134) 1.58/1.61 s(122) =< s(134) 1.58/1.61 s(135) =< s(122)*aux(55) 1.58/1.61 1.58/1.61 with precondition: [V_len>=2] 1.58/1.61 1.58/1.61 1.58/1.61 #### Cost of chains of eval_xnu_start(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B): 1.58/1.61 * Chain [36]: 0 1.58/1.61 with precondition: [] 1.58/1.61 1.58/1.61 * Chain [35]: 0 1.58/1.61 with precondition: [0>=V_len] 1.58/1.61 1.58/1.61 * Chain [34]: 1*s(136)+2*s(139)+10*s(140)+2*s(146)+0 1.58/1.61 Such that:s(136) =< 1 1.58/1.61 s(137) =< V_len 1.58/1.61 s(138) =< V_len/2 1.58/1.61 s(139) =< s(138) 1.58/1.61 s(140) =< s(137) 1.58/1.61 s(139) =< s(137) 1.58/1.61 s(141) =< s(137) 1.58/1.61 s(142) =< s(140)*s(137) 1.58/1.61 s(143) =< s(140)*s(137) 1.58/1.61 s(139) =< s(140)+s(140) 1.58/1.61 s(144) =< s(140)*s(141) 1.58/1.61 s(143) =< s(140)*s(141) 1.58/1.61 s(145) =< s(142) 1.58/1.61 s(145) =< s(144) 1.58/1.61 s(146) =< s(143) 1.58/1.61 s(139) =< s(143) 1.58/1.61 s(146) =< s(145) 1.58/1.61 s(139) =< s(145) 1.58/1.61 s(146) =< s(139)*s(137) 1.58/1.61 1.58/1.61 with precondition: [V_len>=1] 1.58/1.61 1.58/1.61 * Chain [33]: 2*s(149)+12*s(150)+2*s(156)+0 1.58/1.61 Such that:s(148) =< V_len 1.58/1.61 s(147) =< V_len/2 1.58/1.61 s(149) =< s(147) 1.58/1.61 s(149) =< s(148) 1.58/1.61 s(150) =< s(148) 1.58/1.61 s(151) =< s(148) 1.58/1.61 s(152) =< s(150)*s(148) 1.58/1.61 s(153) =< s(150)*s(148) 1.58/1.61 s(149) =< s(150)+s(150) 1.58/1.61 s(154) =< s(150)*s(151) 1.58/1.61 s(153) =< s(150)*s(151) 1.58/1.61 s(155) =< s(152) 1.58/1.61 s(155) =< s(154) 1.58/1.61 s(156) =< s(153) 1.58/1.61 s(149) =< s(153) 1.58/1.61 s(156) =< s(155) 1.58/1.61 s(149) =< s(155) 1.58/1.61 s(156) =< s(149)*s(148) 1.58/1.61 1.58/1.61 with precondition: [V_len>=2] 1.58/1.61 1.58/1.61 1.58/1.61 Closed-form bounds of eval_xnu_start(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B): 1.58/1.61 ------------------------------------- 1.58/1.61 * Chain [36] with precondition: [] 1.58/1.61 - Upper bound: 0 1.58/1.61 - Complexity: constant 1.58/1.61 * Chain [35] with precondition: [0>=V_len] 1.58/1.61 - Upper bound: 0 1.58/1.61 - Complexity: constant 1.58/1.61 * Chain [34] with precondition: [V_len>=1] 1.58/1.61 - Upper bound: 10*V_len+1+2*V_len*V_len+V_len 1.58/1.61 - Complexity: n^2 1.58/1.61 * Chain [33] with precondition: [V_len>=2] 1.58/1.61 - Upper bound: 2*V_len*V_len+12*V_len+V_len 1.58/1.61 - Complexity: n^2 1.58/1.61 1.58/1.61 ### Maximum cost of eval_xnu_start(V__end_0,V_1,V_2,V_4,V_7,V_beg_0,V_end_0,V_i_0,V_k_0,V_len,B): nat(V_len)*2*nat(V_len)+nat(V_len)*10+nat(V_len/2)*2+max([1,nat(V_len)*2]) 1.58/1.61 Asymptotic class: n^2 1.58/1.61 * Total analysis performed in 1438 ms. 1.58/1.61 1.61/1.71 EOF