0.05/0.53 WORST_CASE(?,O(n^2)) 0.05/0.53 0.05/0.53 Preprocessing Cost Relations 0.05/0.53 ===================================== 0.05/0.53 0.05/0.53 #### Computed strongly connected components 0.05/0.53 0. recursive : [eval_realbubble_bb2_in/8,eval_realbubble_bb3_in/8,eval_realbubble_bb4_in/8,eval_realbubble_bb5_in/8] 0.05/0.53 1. recursive : [eval_realbubble_31/11,eval_realbubble_32/11,eval_realbubble_bb1_in/11,eval_realbubble_bb2_in_loop_cont/12,eval_realbubble_bb6_in/11,eval_realbubble_bb7_in/11] 0.05/0.53 2. non_recursive : [eval_realbubble_stop/8] 0.05/0.53 3. non_recursive : [eval_realbubble_bb8_in/8] 0.05/0.53 4. non_recursive : [exit_location/1] 0.05/0.53 5. non_recursive : [eval_realbubble_bb1_in_loop_cont/9] 0.05/0.53 6. non_recursive : [eval_realbubble_10/8] 0.05/0.53 7. non_recursive : [eval_realbubble_9/8] 0.05/0.53 8. non_recursive : [eval_realbubble_8/8] 0.05/0.53 9. non_recursive : [eval_realbubble_7/8] 0.05/0.53 10. non_recursive : [eval_realbubble_6/8] 0.05/0.53 11. non_recursive : [eval_realbubble_5/8] 0.05/0.53 12. non_recursive : [eval_realbubble_4/8] 0.05/0.53 13. non_recursive : [eval_realbubble_3/8] 0.05/0.53 14. non_recursive : [eval_realbubble_2/8] 0.05/0.53 15. non_recursive : [eval_realbubble_1/8] 0.05/0.53 16. non_recursive : [eval_realbubble_bb0_in/8] 0.05/0.53 17. non_recursive : [eval_realbubble_start/8] 0.05/0.53 0.05/0.53 #### Obtained direct recursion through partial evaluation 0.05/0.53 0. SCC is partially evaluated into eval_realbubble_bb2_in/8 0.05/0.53 1. SCC is partially evaluated into eval_realbubble_bb1_in/11 0.05/0.53 2. SCC is completely evaluated into other SCCs 0.05/0.53 3. SCC is completely evaluated into other SCCs 0.05/0.53 4. SCC is completely evaluated into other SCCs 0.05/0.53 5. SCC is partially evaluated into eval_realbubble_bb1_in_loop_cont/9 0.05/0.53 6. SCC is partially evaluated into eval_realbubble_10/8 0.05/0.53 7. SCC is completely evaluated into other SCCs 0.05/0.53 8. SCC is completely evaluated into other SCCs 0.05/0.53 9. SCC is completely evaluated into other SCCs 0.05/0.53 10. SCC is completely evaluated into other SCCs 0.05/0.53 11. SCC is completely evaluated into other SCCs 0.05/0.53 12. SCC is completely evaluated into other SCCs 0.05/0.53 13. SCC is completely evaluated into other SCCs 0.05/0.53 14. SCC is completely evaluated into other SCCs 0.05/0.53 15. SCC is completely evaluated into other SCCs 0.05/0.53 16. SCC is completely evaluated into other SCCs 0.05/0.53 17. SCC is partially evaluated into eval_realbubble_start/8 0.05/0.53 0.05/0.53 Control-Flow Refinement of Cost Relations 0.05/0.53 ===================================== 0.05/0.53 0.05/0.53 ### Specialization of cost equations eval_realbubble_bb2_in/8 0.05/0.53 * CE 14 is refined into CE [15] 0.05/0.53 * CE 13 is refined into CE [16] 0.05/0.53 * CE 11 is refined into CE [17] 0.05/0.53 * CE 12 is refined into CE [18] 0.05/0.53 0.05/0.53 0.05/0.53 ### Cost equations --> "Loop" of eval_realbubble_bb2_in/8 0.05/0.53 * CEs [17] --> Loop 15 0.05/0.53 * CEs [18] --> Loop 16 0.05/0.53 * CEs [15] --> Loop 17 0.05/0.53 * CEs [16] --> Loop 18 0.05/0.53 0.05/0.53 ### Ranking functions of CR eval_realbubble_bb2_in(V_i_0,V_j_0,V_test_0,V_test_1,B,C,D,E) 0.05/0.53 * RF of phase [15,16]: [V_i_0-V_j_0] 0.05/0.53 0.05/0.53 #### Partial ranking functions of CR eval_realbubble_bb2_in(V_i_0,V_j_0,V_test_0,V_test_1,B,C,D,E) 0.05/0.53 * Partial RF of phase [15,16]: 0.05/0.53 - RF of loop [15:1,16:1]: 0.05/0.53 V_i_0-V_j_0 0.05/0.53 0.05/0.53 0.05/0.53 ### Specialization of cost equations eval_realbubble_bb1_in/11 0.05/0.53 * CE 7 is refined into CE [19] 0.05/0.53 * CE 3 is refined into CE [20] 0.05/0.53 * CE 6 is refined into CE [21,22] 0.05/0.53 * CE 8 is refined into CE [23] 0.05/0.53 * CE 5 is refined into CE [24] 0.05/0.53 * CE 4 is discarded (unfeasible) 0.05/0.53 0.05/0.53 0.05/0.53 ### Cost equations --> "Loop" of eval_realbubble_bb1_in/11 0.05/0.53 * CEs [24] --> Loop 19 0.05/0.53 * CEs [19] --> Loop 20 0.05/0.53 * CEs [20] --> Loop 21 0.05/0.53 * CEs [21,22] --> Loop 22 0.05/0.53 * CEs [23] --> Loop 23 0.05/0.53 0.05/0.53 ### Ranking functions of CR eval_realbubble_bb1_in(V_26,V_i_0,V_j_0,V_test_0,V_test_1,B,C,D,E,F,G) 0.05/0.53 * RF of phase [19]: [V_i_0] 0.05/0.53 0.05/0.53 #### Partial ranking functions of CR eval_realbubble_bb1_in(V_26,V_i_0,V_j_0,V_test_0,V_test_1,B,C,D,E,F,G) 0.05/0.53 * Partial RF of phase [19]: 0.05/0.53 - RF of loop [19:1]: 0.05/0.53 V_i_0 0.05/0.53 0.05/0.53 0.05/0.53 ### Specialization of cost equations eval_realbubble_bb1_in_loop_cont/9 0.05/0.53 * CE 9 is refined into CE [25] 0.05/0.53 * CE 10 is refined into CE [26] 0.05/0.53 0.05/0.53 0.05/0.53 ### Cost equations --> "Loop" of eval_realbubble_bb1_in_loop_cont/9 0.05/0.53 * CEs [25] --> Loop 24 0.05/0.53 * CEs [26] --> Loop 25 0.05/0.53 0.05/0.53 ### Ranking functions of CR eval_realbubble_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 0.05/0.53 0.05/0.53 #### Partial ranking functions of CR eval_realbubble_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 0.05/0.53 0.05/0.53 0.05/0.53 ### Specialization of cost equations eval_realbubble_10/8 0.05/0.53 * CE 2 is refined into CE [27,28,29,30,31,32,33] 0.05/0.53 0.05/0.53 0.05/0.53 ### Cost equations --> "Loop" of eval_realbubble_10/8 0.05/0.53 * CEs [29,32] --> Loop 26 0.05/0.53 * CEs [28,30,31] --> Loop 27 0.05/0.53 * CEs [33] --> Loop 28 0.05/0.53 * CEs [27] --> Loop 29 0.05/0.53 0.05/0.53 ### Ranking functions of CR eval_realbubble_10(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B) 0.05/0.53 0.05/0.53 #### Partial ranking functions of CR eval_realbubble_10(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B) 0.05/0.53 0.05/0.53 0.05/0.53 ### Specialization of cost equations eval_realbubble_start/8 0.05/0.53 * CE 1 is refined into CE [34,35,36,37] 0.05/0.53 0.05/0.53 0.05/0.53 ### Cost equations --> "Loop" of eval_realbubble_start/8 0.05/0.53 * CEs [37] --> Loop 30 0.05/0.53 * CEs [36] --> Loop 31 0.05/0.53 * CEs [35] --> Loop 32 0.05/0.53 * CEs [34] --> Loop 33 0.05/0.53 0.05/0.53 ### Ranking functions of CR eval_realbubble_start(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B) 0.05/0.53 0.05/0.53 #### Partial ranking functions of CR eval_realbubble_start(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B) 0.05/0.53 0.05/0.53 0.05/0.53 Computing Bounds 0.05/0.53 ===================================== 0.05/0.53 0.05/0.53 #### Cost of chains of eval_realbubble_bb2_in(V_i_0,V_j_0,V_test_0,V_test_1,B,C,D,E): 0.05/0.53 * Chain [[15,16],18]: 2*it(15)+0 0.05/0.53 Such that:aux(3) =< -V_j_0+C 0.05/0.53 it(15) =< aux(3) 0.05/0.53 0.05/0.53 with precondition: [B=2,V_i_0=C,D=E,V_test_0>=0,D>=0,V_i_0>=V_j_0+1,V_j_0>=V_test_0,V_i_0+V_test_0>=V_j_0+D] 0.05/0.53 0.05/0.53 * Chain [[15,16],17]: 2*it(15)+0 0.05/0.53 Such that:aux(4) =< V_i_0-V_j_0 0.05/0.53 it(15) =< aux(4) 0.05/0.53 0.05/0.53 with precondition: [B=3,V_test_0>=0,V_i_0>=V_j_0+1,V_j_0>=V_test_0] 0.05/0.53 0.05/0.53 * Chain [17]: 0 0.05/0.53 with precondition: [B=3,V_i_0>=1,V_test_0>=0,V_j_0>=V_test_0] 0.05/0.53 0.05/0.53 0.05/0.53 #### Cost of chains of eval_realbubble_bb1_in(V_26,V_i_0,V_j_0,V_test_0,V_test_1,B,C,D,E,F,G): 0.05/0.53 * Chain [[19],23]: 1*it(19)+2*s(5)+0 0.05/0.53 Such that:aux(7) =< V_i_0 0.05/0.53 it(19) =< aux(7) 0.05/0.53 s(6) =< it(19)*aux(7) 0.05/0.53 s(5) =< s(6) 0.05/0.53 0.05/0.53 with precondition: [B=3,V_i_0>=1] 0.05/0.53 0.05/0.53 * Chain [[19],22]: 3*it(19)+2*s(5)+0 0.05/0.53 Such that:aux(8) =< V_i_0 0.05/0.53 it(19) =< aux(8) 0.05/0.53 s(6) =< it(19)*aux(8) 0.05/0.53 s(5) =< s(6) 0.05/0.53 0.05/0.53 with precondition: [B=3,V_i_0>=2] 0.05/0.53 0.05/0.53 * Chain [[19],21]: 1*it(19)+2*s(5)+2*s(10)+0 0.05/0.53 Such that:aux(6) =< V_i_0 0.05/0.53 it(19) =< V_i_0-C 0.05/0.53 s(9) =< C 0.05/0.53 s(10) =< s(9) 0.05/0.53 it(19) =< aux(6) 0.05/0.53 s(6) =< it(19)*aux(6) 0.05/0.53 s(5) =< s(6) 0.05/0.53 0.05/0.53 with precondition: [B=4,F=0,G=0,C=D,C=E,C>=1,V_i_0>=C+1] 0.05/0.53 0.05/0.53 * Chain [[19],20]: 1*it(19)+2*s(5)+0 0.05/0.53 Such that:aux(9) =< V_i_0 0.05/0.53 it(19) =< aux(9) 0.05/0.53 s(6) =< it(19)*aux(9) 0.05/0.53 s(5) =< s(6) 0.05/0.53 0.05/0.53 with precondition: [B=4,C=0,D=0,E=1,F=1,G=1,V_i_0>=1] 0.05/0.53 0.05/0.53 * Chain [23]: 0 0.05/0.53 with precondition: [B=3] 0.05/0.53 0.05/0.53 * Chain [22]: 2*s(8)+0 0.05/0.53 Such that:s(7) =< V_i_0 0.05/0.53 s(8) =< s(7) 0.05/0.53 0.05/0.53 with precondition: [B=3,V_i_0>=1] 0.05/0.53 0.05/0.53 * Chain [21]: 2*s(10)+0 0.05/0.53 Such that:s(9) =< V_i_0 0.05/0.53 s(10) =< s(9) 0.05/0.53 0.05/0.53 with precondition: [B=4,F=0,G=0,C=V_26,V_i_0=D,V_i_0=E,V_i_0>=1] 0.05/0.53 0.05/0.53 * Chain [20]: 0 0.05/0.53 with precondition: [B=4,C=V_26,E=V_j_0,F=V_test_0,G=V_test_1,V_i_0=D,0>=V_i_0] 0.05/0.53 0.05/0.53 0.05/0.53 #### Cost of chains of eval_realbubble_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I): 0.05/0.53 * Chain [25]: 0 0.05/0.53 with precondition: [A=3,F=B+1] 0.05/0.53 0.05/0.53 * Chain [24]: 0 0.05/0.53 with precondition: [A=4,F=B+1] 0.05/0.53 0.05/0.53 0.05/0.53 #### Cost of chains of eval_realbubble_10(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B): 0.05/0.53 * Chain [29]: 0 0.05/0.53 with precondition: [V_length=V_1+1] 0.05/0.53 0.05/0.53 * Chain [28]: 0 0.05/0.53 with precondition: [V_length=V_1+1,1>=V_length] 0.05/0.53 0.05/0.53 * Chain [27]: 6*s(18)+4*s(20)+0 0.05/0.53 Such that:aux(11) =< V_length 0.05/0.53 s(18) =< aux(11) 0.05/0.53 s(19) =< s(18)*aux(11) 0.05/0.53 s(20) =< s(19) 0.05/0.53 0.05/0.53 with precondition: [V_length=V_1+1,V_length>=2] 0.05/0.53 0.05/0.53 * Chain [26]: 6*s(28)+4*s(30)+0 0.05/0.53 Such that:aux(13) =< V_length 0.05/0.53 s(28) =< aux(13) 0.05/0.53 s(29) =< s(28)*aux(13) 0.05/0.53 s(30) =< s(29) 0.05/0.53 0.05/0.53 with precondition: [V_length=V_1+1,V_length>=3] 0.05/0.53 0.05/0.53 0.05/0.53 #### Cost of chains of eval_realbubble_start(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B): 0.05/0.53 * Chain [33]: 0 0.05/0.53 with precondition: [] 0.05/0.53 0.05/0.53 * Chain [32]: 0 0.05/0.53 with precondition: [1>=V_length] 0.05/0.53 0.05/0.53 * Chain [31]: 6*s(38)+4*s(40)+0 0.05/0.53 Such that:s(37) =< V_length 0.05/0.53 s(38) =< s(37) 0.05/0.53 s(39) =< s(38)*s(37) 0.05/0.53 s(40) =< s(39) 0.05/0.53 0.05/0.53 with precondition: [V_length>=2] 0.05/0.53 0.05/0.53 * Chain [30]: 6*s(42)+4*s(44)+0 0.05/0.53 Such that:s(41) =< V_length 0.05/0.53 s(42) =< s(41) 0.05/0.53 s(43) =< s(42)*s(41) 0.05/0.53 s(44) =< s(43) 0.05/0.53 0.05/0.53 with precondition: [V_length>=3] 0.05/0.53 0.05/0.53 0.05/0.53 Closed-form bounds of eval_realbubble_start(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B): 0.05/0.53 ------------------------------------- 0.05/0.53 * Chain [33] with precondition: [] 0.05/0.53 - Upper bound: 0 0.05/0.53 - Complexity: constant 0.05/0.53 * Chain [32] with precondition: [1>=V_length] 0.05/0.53 - Upper bound: 0 0.05/0.53 - Complexity: constant 0.05/0.53 * Chain [31] with precondition: [V_length>=2] 0.05/0.53 - Upper bound: 4*V_length*V_length+6*V_length 0.05/0.53 - Complexity: n^2 0.05/0.53 * Chain [30] with precondition: [V_length>=3] 0.05/0.53 - Upper bound: 4*V_length*V_length+6*V_length 0.05/0.53 - Complexity: n^2 0.05/0.53 0.05/0.53 ### Maximum cost of eval_realbubble_start(V_1,V_26,V_i_0,V_j_0,V_length,V_test_0,V_test_1,B): nat(V_length)*4*nat(V_length)+nat(V_length)*6 0.05/0.53 Asymptotic class: n^2 0.05/0.53 * Total analysis performed in 441 ms. 0.05/0.53 0.54/0.63 EOF