1.23/1.26 WORST_CASE(?,O(n^3)) 1.23/1.26 1.23/1.26 Preprocessing Cost Relations 1.23/1.26 ===================================== 1.23/1.26 1.23/1.26 #### Computed strongly connected components 1.23/1.26 0. recursive : [eval_realshellsort_bb4_in/5,eval_realshellsort_bb5_in/5,eval_realshellsort_bb6_in/5] 1.23/1.26 1. recursive : [eval_realshellsort_27/12,eval_realshellsort_28/12,eval_realshellsort__critedge_in/12,eval_realshellsort_bb2_in/12,eval_realshellsort_bb3_in/12,eval_realshellsort_bb4_in_loop_cont/13] 1.23/1.26 2. recursive : [eval_realshellsort_bb1_in/14,eval_realshellsort_bb2_in_loop_cont/15] 1.23/1.26 3. non_recursive : [eval_realshellsort_stop/8] 1.23/1.26 4. non_recursive : [eval_realshellsort_bb7_in/8] 1.23/1.26 5. non_recursive : [exit_location/1] 1.23/1.26 6. non_recursive : [eval_realshellsort_bb1_in_loop_cont/9] 1.23/1.26 7. non_recursive : [eval_realshellsort_7/8] 1.23/1.26 8. non_recursive : [eval_realshellsort_6/8] 1.23/1.26 9. non_recursive : [eval_realshellsort_5/8] 1.23/1.26 10. non_recursive : [eval_realshellsort_4/8] 1.23/1.26 11. non_recursive : [eval_realshellsort_3/8] 1.23/1.26 12. non_recursive : [eval_realshellsort_2/8] 1.23/1.26 13. non_recursive : [eval_realshellsort_1/8] 1.23/1.26 14. non_recursive : [eval_realshellsort_0/8] 1.23/1.26 15. non_recursive : [eval_realshellsort_bb0_in/8] 1.23/1.26 16. non_recursive : [eval_realshellsort_start/8] 1.23/1.26 1.23/1.26 #### Obtained direct recursion through partial evaluation 1.23/1.26 0. SCC is partially evaluated into eval_realshellsort_bb4_in/5 1.23/1.26 1. SCC is partially evaluated into eval_realshellsort_bb2_in/12 1.23/1.26 2. SCC is partially evaluated into eval_realshellsort_bb1_in/14 1.23/1.26 3. SCC is completely evaluated into other SCCs 1.23/1.26 4. SCC is completely evaluated into other SCCs 1.23/1.26 5. SCC is completely evaluated into other SCCs 1.23/1.26 6. SCC is partially evaluated into eval_realshellsort_bb1_in_loop_cont/9 1.23/1.26 7. SCC is partially evaluated into eval_realshellsort_7/8 1.23/1.26 8. SCC is completely evaluated into other SCCs 1.23/1.26 9. SCC is completely evaluated into other SCCs 1.23/1.26 10. SCC is completely evaluated into other SCCs 1.23/1.26 11. SCC is completely evaluated into other SCCs 1.23/1.26 12. SCC is completely evaluated into other SCCs 1.23/1.26 13. SCC is completely evaluated into other SCCs 1.23/1.26 14. SCC is completely evaluated into other SCCs 1.23/1.26 15. SCC is completely evaluated into other SCCs 1.23/1.26 16. SCC is partially evaluated into eval_realshellsort_start/8 1.23/1.26 1.23/1.26 Control-Flow Refinement of Cost Relations 1.23/1.26 ===================================== 1.23/1.26 1.23/1.26 ### Specialization of cost equations eval_realshellsort_bb4_in/5 1.23/1.26 * CE 18 is refined into CE [19] 1.23/1.26 * CE 17 is refined into CE [20] 1.23/1.26 * CE 15 is refined into CE [21] 1.23/1.26 * CE 16 is refined into CE [22] 1.23/1.26 1.23/1.26 1.23/1.26 ### Cost equations --> "Loop" of eval_realshellsort_bb4_in/5 1.23/1.26 * CEs [22] --> Loop 19 1.23/1.26 * CEs [19] --> Loop 20 1.23/1.26 * CEs [20] --> Loop 21 1.23/1.26 * CEs [21] --> Loop 22 1.23/1.26 1.23/1.26 ### Ranking functions of CR eval_realshellsort_bb4_in(V_0,V_5,V_j_0,B,C) 1.23/1.26 * RF of phase [19]: [-V_0+V_j_0+1,V_j_0] 1.23/1.26 1.23/1.26 #### Partial ranking functions of CR eval_realshellsort_bb4_in(V_0,V_5,V_j_0,B,C) 1.23/1.26 * Partial RF of phase [19]: 1.23/1.26 - RF of loop [19:1]: 1.23/1.26 -V_0+V_j_0+1 1.23/1.26 V_j_0 1.23/1.26 1.23/1.26 1.23/1.26 ### Specialization of cost equations eval_realshellsort_bb2_in/12 1.23/1.26 * CE 13 is refined into CE [23] 1.23/1.26 * CE 11 is refined into CE [24,25] 1.23/1.26 * CE 14 is refined into CE [26] 1.23/1.26 * CE 12 is refined into CE [27,28,29,30] 1.23/1.26 1.23/1.26 1.23/1.26 ### Cost equations --> "Loop" of eval_realshellsort_bb2_in/12 1.23/1.26 * CEs [30] --> Loop 23 1.23/1.26 * CEs [29] --> Loop 24 1.23/1.26 * CEs [28] --> Loop 25 1.23/1.26 * CEs [27] --> Loop 26 1.23/1.26 * CEs [23] --> Loop 27 1.23/1.26 * CEs [25] --> Loop 28 1.23/1.26 * CEs [24] --> Loop 29 1.23/1.26 * CEs [26] --> Loop 30 1.23/1.26 1.23/1.26 ### Ranking functions of CR eval_realshellsort_bb2_in(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B,C,D,E,F) 1.23/1.26 * RF of phase [23,24,26]: [V_array_size-V_i_0] 1.23/1.26 * RF of phase [25]: [V_0-V_i_0,V_array_size/2-V_i_0-1/2,V_array_size_sink/2-V_i_0-1/2] 1.23/1.26 1.23/1.26 #### Partial ranking functions of CR eval_realshellsort_bb2_in(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B,C,D,E,F) 1.23/1.26 * Partial RF of phase [23,24,26]: 1.23/1.26 - RF of loop [23:1,24:1,26:1]: 1.23/1.26 V_array_size-V_i_0 1.23/1.26 * Partial RF of phase [25]: 1.23/1.26 - RF of loop [25:1]: 1.23/1.26 V_0-V_i_0 1.23/1.26 V_array_size/2-V_i_0-1/2 1.23/1.26 V_array_size_sink/2-V_i_0-1/2 1.23/1.26 1.23/1.26 1.23/1.26 ### Specialization of cost equations eval_realshellsort_bb1_in/14 1.23/1.26 * CE 7 is refined into CE [31] 1.23/1.26 * CE 3 is refined into CE [32,33,34,35] 1.23/1.26 * CE 8 is refined into CE [36] 1.23/1.26 * CE 6 is refined into CE [37] 1.23/1.26 * CE 5 is refined into CE [38] 1.23/1.26 * CE 4 is refined into CE [39] 1.23/1.26 1.23/1.26 1.23/1.26 ### Cost equations --> "Loop" of eval_realshellsort_bb1_in/14 1.23/1.26 * CEs [39] --> Loop 31 1.23/1.26 * CEs [31] --> Loop 32 1.23/1.26 * CEs [36] --> Loop 33 1.23/1.26 * CEs [32,33,35] --> Loop 34 1.23/1.26 * CEs [34] --> Loop 35 1.23/1.26 * CEs [37] --> Loop 36 1.23/1.26 * CEs [38] --> Loop 37 1.23/1.26 1.23/1.26 ### Ranking functions of CR eval_realshellsort_bb1_in(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B,C,D,E,F,G,H) 1.23/1.26 * RF of phase [31]: [V_array_size_sink-1] 1.23/1.26 1.23/1.26 #### Partial ranking functions of CR eval_realshellsort_bb1_in(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B,C,D,E,F,G,H) 1.23/1.26 * Partial RF of phase [31]: 1.23/1.26 - RF of loop [31:1]: 1.23/1.26 V_array_size_sink-1 1.23/1.26 1.23/1.26 1.23/1.26 ### Specialization of cost equations eval_realshellsort_bb1_in_loop_cont/9 1.23/1.26 * CE 9 is refined into CE [40] 1.23/1.26 * CE 10 is refined into CE [41] 1.23/1.26 1.23/1.26 1.23/1.26 ### Cost equations --> "Loop" of eval_realshellsort_bb1_in_loop_cont/9 1.23/1.26 * CEs [40] --> Loop 38 1.23/1.26 * CEs [41] --> Loop 39 1.23/1.26 1.23/1.26 ### Ranking functions of CR eval_realshellsort_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 1.23/1.26 1.23/1.26 #### Partial ranking functions of CR eval_realshellsort_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 1.23/1.26 1.23/1.26 1.23/1.26 ### Specialization of cost equations eval_realshellsort_7/8 1.23/1.26 * CE 2 is refined into CE [42,43,44,45,46,47,48,49] 1.23/1.26 1.23/1.26 1.23/1.26 ### Cost equations --> "Loop" of eval_realshellsort_7/8 1.23/1.26 * CEs [46] --> Loop 40 1.23/1.26 * CEs [44] --> Loop 41 1.23/1.26 * CEs [45,48] --> Loop 42 1.23/1.26 * CEs [49] --> Loop 43 1.23/1.26 * CEs [43] --> Loop 44 1.23/1.26 * CEs [42] --> Loop 45 1.23/1.26 * CEs [47] --> Loop 46 1.23/1.26 1.23/1.26 ### Ranking functions of CR eval_realshellsort_7(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B) 1.23/1.26 1.23/1.26 #### Partial ranking functions of CR eval_realshellsort_7(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B) 1.23/1.26 1.23/1.26 1.23/1.26 ### Specialization of cost equations eval_realshellsort_start/8 1.23/1.26 * CE 1 is refined into CE [50,51,52,53,54,55,56] 1.23/1.26 1.23/1.26 1.23/1.26 ### Cost equations --> "Loop" of eval_realshellsort_start/8 1.23/1.26 * CEs [56] --> Loop 47 1.23/1.26 * CEs [55] --> Loop 48 1.23/1.26 * CEs [54] --> Loop 49 1.23/1.26 * CEs [53] --> Loop 50 1.23/1.26 * CEs [52] --> Loop 51 1.23/1.26 * CEs [51] --> Loop 52 1.23/1.26 * CEs [50] --> Loop 53 1.23/1.26 1.23/1.26 ### Ranking functions of CR eval_realshellsort_start(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B) 1.23/1.26 1.23/1.26 #### Partial ranking functions of CR eval_realshellsort_start(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B) 1.23/1.26 1.23/1.26 1.23/1.26 Computing Bounds 1.23/1.26 ===================================== 1.23/1.26 1.23/1.26 #### Cost of chains of eval_realshellsort_bb4_in(V_0,V_5,V_j_0,B,C): 1.23/1.26 * Chain [[19],22]: 1*it(19)+0 1.23/1.26 Such that:it(19) =< V_j_0-C 1.23/1.26 1.23/1.26 with precondition: [B=2,V_0>=1,C>=V_0,V_j_0>=V_0+C] 1.23/1.26 1.23/1.26 * Chain [[19],21]: 1*it(19)+0 1.23/1.26 Such that:it(19) =< -V_0+V_j_0+1 1.23/1.26 1.23/1.26 with precondition: [B=2,C>=0,V_0>=C+1,V_j_0>=V_0+C] 1.23/1.26 1.23/1.26 * Chain [[19],20]: 1*it(19)+0 1.23/1.26 Such that:it(19) =< -V_0+V_j_0+1 1.23/1.26 1.23/1.26 with precondition: [B=3,V_0>=1,V_j_0>=V_0] 1.23/1.26 1.23/1.26 * Chain [22]: 0 1.23/1.26 with precondition: [B=2,V_j_0=C,V_0>=1,V_j_0>=V_0] 1.23/1.26 1.23/1.26 * Chain [21]: 0 1.23/1.26 with precondition: [B=2,V_j_0=C,V_j_0>=0,V_0>=V_j_0+1] 1.23/1.26 1.23/1.26 * Chain [20]: 0 1.23/1.26 with precondition: [B=3,V_0>=1,V_j_0>=0] 1.23/1.26 1.23/1.26 1.23/1.26 #### Cost of chains of eval_realshellsort_bb2_in(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B,C,D,E,F): 1.23/1.26 * Chain [[25],[23,24,26],30]: 3*it(23)+1*it(25)+1*s(5)+1*s(6)+0 1.23/1.26 Such that:it(25) =< V_0-V_i_0 1.23/1.26 aux(6) =< -V_0+V_array_size 1.23/1.26 it(23) =< aux(6) 1.23/1.26 aux(2) =< aux(6) 1.23/1.26 s(5) =< it(23)*aux(6) 1.23/1.26 s(6) =< it(23)*aux(2) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_0>=V_i_0+1] 1.23/1.26 1.23/1.26 * Chain [[25],[23,24,26],29]: 3*it(23)+1*it(25)+1*s(5)+1*s(6)+0 1.23/1.26 Such that:it(25) =< V_0-V_i_0 1.23/1.26 aux(8) =< -V_0+V_array_size 1.23/1.26 it(23) =< aux(8) 1.23/1.26 aux(2) =< aux(8) 1.23/1.26 s(5) =< it(23)*aux(8) 1.23/1.26 s(6) =< it(23)*aux(2) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_0+2,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_0>=V_i_0+1] 1.23/1.26 1.23/1.26 * Chain [[25],[23,24,26],28]: 4*it(23)+1*it(25)+1*s(5)+1*s(6)+0 1.23/1.26 Such that:it(25) =< V_0-V_i_0 1.23/1.26 aux(11) =< -V_0+V_array_size 1.23/1.26 it(23) =< aux(11) 1.23/1.26 aux(2) =< aux(11) 1.23/1.26 s(5) =< it(23)*aux(11) 1.23/1.26 s(6) =< it(23)*aux(2) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_0+2,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_0>=V_i_0+1] 1.23/1.26 1.23/1.26 * Chain [[25],[23,24,26],27]: 3*it(23)+1*it(25)+1*s(5)+1*s(6)+0 1.23/1.26 Such that:it(25) =< V_0-V_i_0 1.23/1.26 aux(13) =< -V_0+E 1.23/1.26 it(23) =< aux(13) 1.23/1.26 aux(2) =< aux(13) 1.23/1.26 s(5) =< it(23)*aux(13) 1.23/1.26 s(6) =< it(23)*aux(2) 1.23/1.26 1.23/1.26 with precondition: [B=4,V_array_size=C,V_array_size=E,V_i_0>=0,F>=0,V_array_size_sink>=2*V_0,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_0>=V_i_0+1,V_array_size>=F+1] 1.23/1.26 1.23/1.26 * Chain [[25],30]: 1*it(25)+0 1.23/1.26 Such that:it(25) =< V_0-V_i_0 1.23/1.26 1.23/1.26 with precondition: [B=3,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_0>=V_i_0+1] 1.23/1.26 1.23/1.26 * Chain [[25],29]: 1*it(25)+0 1.23/1.26 Such that:it(25) =< V_0-V_i_0 1.23/1.26 1.23/1.26 with precondition: [B=3,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_0>=V_i_0+1] 1.23/1.26 1.23/1.26 * Chain [[25],28]: 1*it(25)+1*s(7)+0 1.23/1.26 Such that:s(7) =< 1 1.23/1.26 it(25) =< V_0-V_i_0 1.23/1.26 1.23/1.26 with precondition: [B=3,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_0>=V_i_0+1] 1.23/1.26 1.23/1.26 * Chain [30]: 0 1.23/1.26 with precondition: [B=3,V_0>=1,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink] 1.23/1.26 1.23/1.26 * Chain [29]: 0 1.23/1.26 with precondition: [B=3,V_0>=1,V_i_0>=0,V_array_size_sink>=2*V_0,V_array_size>=V_array_size_sink,2*V_0+1>=V_array_size_sink,V_array_size>=V_i_0+1] 1.23/1.26 1.23/1.26 1.23/1.26 #### Cost of chains of eval_realshellsort_bb1_in(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B,C,D,E,F,G,H): 1.23/1.26 * Chain [[31],36]: 2*it(31)+3*s(43)+1*s(44)+1*s(45)+0 1.23/1.26 Such that:aux(18) =< G 1.23/1.26 aux(21) =< V_array_size_sink 1.23/1.26 aux(17) =< aux(18) 1.23/1.26 it(31) =< aux(21) 1.23/1.26 aux(17) =< aux(18) 1.23/1.26 s(46) =< it(31)*aux(17) 1.23/1.26 s(43) =< s(46) 1.23/1.26 s(39) =< aux(18) 1.23/1.26 s(44) =< s(43)*aux(18) 1.23/1.26 s(45) =< s(43)*s(39) 1.23/1.26 1.23/1.26 with precondition: [B=5,C=1,F=1,V_array_size=D,V_array_size=G,V_array_size_sink>=2,H>=0,V_array_size>=V_array_size_sink,V_array_size>=H+1] 1.23/1.26 1.23/1.26 * Chain [[31],35]: 2*it(31)+3*s(43)+1*s(44)+1*s(45)+2*s(49)+7*s(50)+2*s(52)+2*s(53)+0 1.23/1.26 Such that:aux(23) =< V_array_size 1.23/1.26 aux(24) =< V_array_size+1/2 1.23/1.26 aux(25) =< V_array_size_sink 1.23/1.26 s(47) =< aux(23) 1.23/1.26 s(47) =< aux(24) 1.23/1.26 s(48) =< aux(24) 1.23/1.26 s(48) =< aux(25) 1.23/1.26 s(48) =< aux(23) 1.23/1.26 s(49) =< s(48) 1.23/1.26 s(50) =< s(47) 1.23/1.26 s(51) =< s(47) 1.23/1.26 s(52) =< s(50)*s(47) 1.23/1.26 s(53) =< s(50)*s(51) 1.23/1.26 aux(17) =< aux(23) 1.23/1.26 it(31) =< aux(25) 1.23/1.26 aux(17) =< aux(23) 1.23/1.26 s(46) =< it(31)*aux(17) 1.23/1.26 s(43) =< s(46) 1.23/1.26 s(39) =< aux(23) 1.23/1.26 s(44) =< s(43)*aux(23) 1.23/1.26 s(45) =< s(43)*s(39) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_array_size_sink>=4,V_array_size>=V_array_size_sink] 1.23/1.26 1.23/1.26 * Chain [[31],34]: 2*it(31)+3*s(43)+1*s(44)+1*s(45)+1*s(54)+4*s(57)+3*s(58)+1*s(60)+1*s(61)+0 1.23/1.26 Such that:s(54) =< 1 1.23/1.26 s(56) =< V_array_size_sink/4 1.23/1.26 aux(27) =< V_array_size 1.23/1.26 aux(28) =< V_array_size_sink 1.23/1.26 s(56) =< aux(28) 1.23/1.26 s(56) =< aux(27) 1.23/1.26 s(57) =< s(56) 1.23/1.26 s(58) =< aux(27) 1.23/1.26 s(39) =< aux(27) 1.23/1.26 s(60) =< s(58)*aux(27) 1.23/1.26 s(61) =< s(58)*s(39) 1.23/1.26 aux(17) =< aux(27) 1.23/1.26 it(31) =< aux(28) 1.23/1.26 aux(17) =< aux(27) 1.23/1.26 s(46) =< it(31)*aux(17) 1.23/1.26 s(43) =< s(46) 1.23/1.26 s(44) =< s(43)*aux(27) 1.23/1.26 s(45) =< s(43)*s(39) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_array_size_sink>=4,V_array_size>=V_array_size_sink] 1.23/1.26 1.23/1.26 * Chain [[31],33]: 2*it(31)+3*s(43)+1*s(44)+1*s(45)+0 1.23/1.26 Such that:aux(18) =< V_array_size 1.23/1.26 aux(29) =< V_array_size_sink 1.23/1.26 aux(17) =< aux(18) 1.23/1.26 it(31) =< aux(29) 1.23/1.26 aux(17) =< aux(18) 1.23/1.26 s(46) =< it(31)*aux(17) 1.23/1.26 s(43) =< s(46) 1.23/1.26 s(39) =< aux(18) 1.23/1.26 s(44) =< s(43)*aux(18) 1.23/1.26 s(45) =< s(43)*s(39) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_array_size_sink>=2,V_array_size>=V_array_size_sink] 1.23/1.26 1.23/1.26 * Chain [37]: 0 1.23/1.26 with precondition: [V_array_size=0,V_array_size_sink=0,B=5,F=0,C=V_0,D=V_21,E=V_5,G=V_i_0,H=V_j_0] 1.23/1.26 1.23/1.26 * Chain [36]: 0 1.23/1.26 with precondition: [V_array_size_sink=1,B=5,F=1,C=V_0,D=V_21,E=V_5,G=V_i_0,H=V_j_0,V_array_size>=1] 1.23/1.26 1.23/1.26 * Chain [35]: 2*s(49)+7*s(50)+2*s(52)+2*s(53)+0 1.23/1.26 Such that:s(47) =< V_array_size-V_array_size_sink/2+1/2 1.23/1.26 s(48) =< V_array_size_sink/2 1.23/1.26 aux(22) =< V_array_size 1.23/1.26 s(47) =< aux(22) 1.23/1.26 s(48) =< aux(22) 1.23/1.26 s(49) =< s(48) 1.23/1.26 s(50) =< s(47) 1.23/1.26 s(51) =< s(47) 1.23/1.26 s(52) =< s(50)*s(47) 1.23/1.26 s(53) =< s(50)*s(51) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_array_size>=3,V_array_size_sink>=2,V_array_size>=V_array_size_sink] 1.23/1.26 1.23/1.26 * Chain [34]: 1*s(54)+4*s(57)+3*s(58)+1*s(60)+1*s(61)+0 1.23/1.26 Such that:s(54) =< 1 1.23/1.26 aux(26) =< V_array_size 1.23/1.26 s(56) =< V_array_size_sink/2 1.23/1.26 s(56) =< aux(26) 1.23/1.26 s(57) =< s(56) 1.23/1.26 s(58) =< aux(26) 1.23/1.26 s(59) =< aux(26) 1.23/1.26 s(60) =< s(58)*aux(26) 1.23/1.26 s(61) =< s(58)*s(59) 1.23/1.26 1.23/1.26 with precondition: [B=3,V_array_size_sink>=2,V_array_size>=V_array_size_sink] 1.23/1.26 1.23/1.26 * Chain [33]: 0 1.23/1.26 with precondition: [B=3,V_array_size>=V_array_size_sink] 1.23/1.26 1.23/1.26 * Chain [32]: 0 1.23/1.26 with precondition: [B=5,C=V_0,D=V_21,E=V_5,V_array_size_sink=V_array_size,G=V_i_0,H=V_j_0,V_array_size_sink=F,0>=V_array_size_sink+1] 1.23/1.26 1.23/1.26 1.23/1.26 #### Cost of chains of eval_realshellsort_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I): 1.23/1.26 * Chain [39]: 0 1.23/1.26 with precondition: [A=3] 1.23/1.26 1.23/1.26 * Chain [38]: 0 1.23/1.26 with precondition: [A=5] 1.23/1.26 1.23/1.26 1.23/1.26 #### Cost of chains of eval_realshellsort_7(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B): 1.23/1.26 * Chain [46]: 0 1.23/1.26 with precondition: [] 1.23/1.26 1.23/1.26 * Chain [45]: 0 1.23/1.26 with precondition: [V_array_size=0] 1.23/1.26 1.23/1.26 * Chain [44]: 0 1.23/1.26 with precondition: [V_array_size=1] 1.23/1.26 1.23/1.26 * Chain [43]: 0 1.23/1.26 with precondition: [0>=V_array_size+1] 1.23/1.26 1.23/1.26 * Chain [42]: 1*s(111)+4*s(115)+7*s(116)+1*s(118)+1*s(119)+6*s(123)+2*s(124)+2*s(125)+0 1.23/1.26 Such that:s(111) =< 1 1.23/1.26 s(113) =< V_array_size/2 1.23/1.26 aux(35) =< V_array_size 1.23/1.26 s(113) =< aux(35) 1.23/1.26 s(115) =< s(113) 1.23/1.26 s(116) =< aux(35) 1.23/1.26 s(117) =< aux(35) 1.23/1.26 s(118) =< s(116)*aux(35) 1.23/1.26 s(119) =< s(116)*s(117) 1.23/1.26 s(120) =< aux(35) 1.23/1.26 s(120) =< aux(35) 1.23/1.26 s(122) =< s(116)*s(120) 1.23/1.26 s(123) =< s(122) 1.23/1.26 s(124) =< s(123)*aux(35) 1.23/1.26 s(125) =< s(123)*s(117) 1.23/1.26 1.23/1.26 with precondition: [V_array_size>=2] 1.23/1.26 1.23/1.26 * Chain [41]: 2*s(138)+7*s(139)+2*s(141)+2*s(142)+0 1.23/1.26 Such that:s(137) =< V_array_size 1.23/1.26 s(136) =< V_array_size/2 1.23/1.26 s(135) =< V_array_size/2+1/2 1.23/1.26 s(135) =< s(137) 1.23/1.26 s(136) =< s(137) 1.23/1.26 s(138) =< s(136) 1.23/1.26 s(139) =< s(135) 1.23/1.26 s(140) =< s(135) 1.23/1.26 s(141) =< s(139)*s(135) 1.23/1.26 s(142) =< s(139)*s(140) 1.23/1.26 1.23/1.26 with precondition: [V_array_size>=3] 1.23/1.26 1.23/1.26 * Chain [40]: 1*s(143)+4*s(148)+7*s(149)+1*s(151)+1*s(152)+6*s(156)+2*s(157)+2*s(158)+9*s(161)+2*s(164)+2*s(165)+0 1.23/1.26 Such that:s(143) =< 1 1.23/1.26 s(144) =< V_array_size+1/2 1.23/1.26 s(145) =< V_array_size/4 1.23/1.26 aux(36) =< V_array_size 1.23/1.26 s(145) =< aux(36) 1.23/1.26 s(148) =< s(145) 1.23/1.26 s(149) =< aux(36) 1.23/1.26 s(150) =< aux(36) 1.23/1.26 s(151) =< s(149)*aux(36) 1.23/1.26 s(152) =< s(149)*s(150) 1.23/1.26 s(153) =< aux(36) 1.23/1.26 s(153) =< aux(36) 1.23/1.26 s(155) =< s(149)*s(153) 1.23/1.26 s(156) =< s(155) 1.23/1.26 s(157) =< s(156)*aux(36) 1.23/1.26 s(158) =< s(156)*s(150) 1.23/1.26 s(159) =< aux(36) 1.23/1.26 s(159) =< s(144) 1.23/1.26 s(161) =< s(159) 1.23/1.26 s(163) =< s(159) 1.23/1.26 s(164) =< s(161)*s(159) 1.23/1.26 s(165) =< s(161)*s(163) 1.23/1.26 1.23/1.26 with precondition: [V_array_size>=4] 1.23/1.26 1.23/1.26 1.23/1.26 #### Cost of chains of eval_realshellsort_start(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B): 1.23/1.26 * Chain [53]: 0 1.23/1.26 with precondition: [] 1.23/1.26 1.23/1.26 * Chain [52]: 0 1.23/1.26 with precondition: [V_array_size=0] 1.23/1.26 1.23/1.26 * Chain [51]: 0 1.23/1.26 with precondition: [V_array_size=1] 1.23/1.26 1.23/1.26 * Chain [50]: 0 1.23/1.26 with precondition: [0>=V_array_size+1] 1.23/1.26 1.23/1.26 * Chain [49]: 1*s(166)+4*s(169)+7*s(170)+1*s(172)+1*s(173)+6*s(176)+2*s(177)+2*s(178)+0 1.23/1.26 Such that:s(166) =< 1 1.23/1.26 s(168) =< V_array_size 1.23/1.26 s(167) =< V_array_size/2 1.23/1.26 s(167) =< s(168) 1.23/1.26 s(169) =< s(167) 1.23/1.26 s(170) =< s(168) 1.23/1.26 s(171) =< s(168) 1.23/1.26 s(172) =< s(170)*s(168) 1.23/1.26 s(173) =< s(170)*s(171) 1.23/1.26 s(174) =< s(168) 1.23/1.26 s(174) =< s(168) 1.23/1.26 s(175) =< s(170)*s(174) 1.23/1.26 s(176) =< s(175) 1.23/1.26 s(177) =< s(176)*s(168) 1.23/1.26 s(178) =< s(176)*s(171) 1.23/1.26 1.23/1.26 with precondition: [V_array_size>=2] 1.23/1.26 1.23/1.26 * Chain [48]: 2*s(182)+7*s(183)+2*s(185)+2*s(186)+0 1.23/1.26 Such that:s(179) =< V_array_size 1.23/1.26 s(180) =< V_array_size/2 1.23/1.26 s(181) =< V_array_size/2+1/2 1.23/1.26 s(181) =< s(179) 1.23/1.26 s(180) =< s(179) 1.23/1.26 s(182) =< s(180) 1.23/1.26 s(183) =< s(181) 1.23/1.26 s(184) =< s(181) 1.23/1.26 s(185) =< s(183)*s(181) 1.23/1.26 s(186) =< s(183)*s(184) 1.23/1.26 1.23/1.26 with precondition: [V_array_size>=3] 1.23/1.26 1.23/1.26 * Chain [47]: 1*s(187)+4*s(191)+7*s(192)+1*s(194)+1*s(195)+6*s(198)+2*s(199)+2*s(200)+9*s(202)+2*s(204)+2*s(205)+0 1.23/1.26 Such that:s(187) =< 1 1.23/1.26 s(190) =< V_array_size 1.23/1.26 s(188) =< V_array_size+1/2 1.23/1.26 s(189) =< V_array_size/4 1.23/1.26 s(189) =< s(190) 1.23/1.26 s(191) =< s(189) 1.23/1.26 s(192) =< s(190) 1.23/1.26 s(193) =< s(190) 1.23/1.26 s(194) =< s(192)*s(190) 1.23/1.26 s(195) =< s(192)*s(193) 1.23/1.26 s(196) =< s(190) 1.23/1.26 s(196) =< s(190) 1.23/1.26 s(197) =< s(192)*s(196) 1.23/1.26 s(198) =< s(197) 1.23/1.26 s(199) =< s(198)*s(190) 1.23/1.26 s(200) =< s(198)*s(193) 1.23/1.26 s(201) =< s(190) 1.23/1.26 s(201) =< s(188) 1.23/1.26 s(202) =< s(201) 1.23/1.26 s(203) =< s(201) 1.23/1.26 s(204) =< s(202)*s(201) 1.23/1.26 s(205) =< s(202)*s(203) 1.23/1.26 1.23/1.26 with precondition: [V_array_size>=4] 1.23/1.26 1.23/1.26 1.23/1.26 Closed-form bounds of eval_realshellsort_start(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B): 1.23/1.26 ------------------------------------- 1.23/1.26 * Chain [53] with precondition: [] 1.23/1.26 - Upper bound: 0 1.23/1.26 - Complexity: constant 1.23/1.26 * Chain [52] with precondition: [V_array_size=0] 1.23/1.26 - Upper bound: 0 1.23/1.26 - Complexity: constant 1.23/1.26 * Chain [51] with precondition: [V_array_size=1] 1.23/1.26 - Upper bound: 0 1.23/1.26 - Complexity: constant 1.23/1.26 * Chain [50] with precondition: [0>=V_array_size+1] 1.23/1.26 - Upper bound: 0 1.23/1.26 - Complexity: constant 1.23/1.26 * Chain [49] with precondition: [V_array_size>=2] 1.23/1.26 - Upper bound: 7*V_array_size+1+8*V_array_size*V_array_size+4*V_array_size*V_array_size*V_array_size+2*V_array_size 1.23/1.26 - Complexity: n^3 1.23/1.26 * Chain [48] with precondition: [V_array_size>=3] 1.23/1.26 - Upper bound: 7/2*V_array_size+7/2+(V_array_size/2+1/2)*(2*V_array_size+2)+V_array_size 1.23/1.26 - Complexity: n^2 1.23/1.26 * Chain [47] with precondition: [V_array_size>=4] 1.23/1.26 - Upper bound: 16*V_array_size+1+12*V_array_size*V_array_size+4*V_array_size*V_array_size*V_array_size+V_array_size 1.23/1.26 - Complexity: n^3 1.23/1.26 1.23/1.26 ### Maximum cost of eval_realshellsort_start(V_0,V_21,V_5,V_array_size,V_array_size_sink,V_i_0,V_j_0,B): max([nat(V_array_size/2+1/2)*4*nat(V_array_size/2+1/2)+nat(V_array_size/2+1/2)*7+nat(V_array_size/2)*2,nat(V_array_size)*7+1+nat(V_array_size)*8*nat(V_array_size)+nat(V_array_size)*4*nat(V_array_size)*nat(V_array_size)+max([nat(V_array_size/2)*4,nat(V_array_size)*4*nat(V_array_size)+nat(V_array_size)*9+nat(V_array_size/4)*4])]) 1.23/1.26 Asymptotic class: n^3 1.23/1.26 * Total analysis performed in 1142 ms. 1.23/1.26 1.26/1.36 EOF