WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). (0) CpxRelTRS (1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 165 ms] (2) CpxRelTRS (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxWeightedTrs (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxTypedWeightedTrs (7) CompletionProof [UPPER BOUND(ID), 0 ms] (8) CpxTypedWeightedCompleteTrs (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 15 ms] (10) CpxRNTS (11) CompleteCoflocoProof [FINISHED, 6189 ms] (12) BOUNDS(1, n^2) (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (14) TRS for Loop Detection (15) DecreasingLoopProof [LOWER BOUND(ID), 133 ms] (16) BEST (17) proven lower bound (18) LowerBoundPropagationProof [FINISHED, 0 ms] (19) BOUNDS(n^1, INF) (20) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #abs(#0) -> #0 #abs(#neg(@x)) -> #pos(@x) #abs(#pos(@x)) -> #pos(@x) #abs(#s(@x)) -> #pos(#s(@x)) #less(@x, @y) -> #cklt(#compare(@x, @y)) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insertD(@x, @l) -> insertD#1(@l, @x) insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) insertD#1(nil, @x) -> ::(@x, nil) insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) insertionsort(@l) -> insertionsort#1(@l) insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) insertionsort#1(nil) -> nil insertionsortD(@l) -> insertionsortD#1(@l) insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) insertionsortD#1(nil) -> nil testInsertionsort(@x) -> insertionsort(testList(#unit)) testInsertionsortD(@x) -> insertionsortD(testList(#unit)) testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) The (relative) TRS S consists of the following rules: #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) Rewrite Strategy: INNERMOST ---------------------------------------- (1) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #abs(#0) -> #0 #abs(#neg(@x)) -> #pos(@x) #abs(#pos(@x)) -> #pos(@x) #abs(#s(@x)) -> #pos(#s(@x)) #less(@x, @y) -> #cklt(#compare(@x, @y)) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insertD(@x, @l) -> insertD#1(@l, @x) insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) insertD#1(nil, @x) -> ::(@x, nil) insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) insertionsort(@l) -> insertionsort#1(@l) insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) insertionsort#1(nil) -> nil insertionsortD(@l) -> insertionsortD#1(@l) insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) insertionsortD#1(nil) -> nil testInsertionsort(@x) -> insertionsort(testList(#unit)) testInsertionsortD(@x) -> insertionsortD(testList(#unit)) testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) The (relative) TRS S consists of the following rules: #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) Rewrite Strategy: INNERMOST ---------------------------------------- (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: #abs(#0) -> #0 [1] #abs(#neg(@x)) -> #pos(@x) [1] #abs(#pos(@x)) -> #pos(@x) [1] #abs(#s(@x)) -> #pos(#s(@x)) [1] #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] insert(@x, @l) -> insert#1(@l, @x) [1] insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) [1] insert#1(nil, @x) -> ::(@x, nil) [1] insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) [1] insertD(@x, @l) -> insertD#1(@l, @x) [1] insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) [1] insertD#1(nil, @x) -> ::(@x, nil) [1] insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) [1] insertionsort(@l) -> insertionsort#1(@l) [1] insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) [1] insertionsort#1(nil) -> nil [1] insertionsortD(@l) -> insertionsortD#1(@l) [1] insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) [1] insertionsortD#1(nil) -> nil [1] testInsertionsort(@x) -> insertionsort(testList(#unit)) [1] testInsertionsortD(@x) -> insertionsortD(testList(#unit)) [1] testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) [1] #cklt(#EQ) -> #false [0] #cklt(#GT) -> #false [0] #cklt(#LT) -> #true [0] #compare(#0, #0) -> #EQ [0] #compare(#0, #neg(@y)) -> #GT [0] #compare(#0, #pos(@y)) -> #LT [0] #compare(#0, #s(@y)) -> #LT [0] #compare(#neg(@x), #0) -> #LT [0] #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] #compare(#neg(@x), #pos(@y)) -> #LT [0] #compare(#pos(@x), #0) -> #GT [0] #compare(#pos(@x), #neg(@y)) -> #GT [0] #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] #compare(#s(@x), #0) -> #GT [0] #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (6) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: #abs(#0) -> #0 [1] #abs(#neg(@x)) -> #pos(@x) [1] #abs(#pos(@x)) -> #pos(@x) [1] #abs(#s(@x)) -> #pos(#s(@x)) [1] #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] insert(@x, @l) -> insert#1(@l, @x) [1] insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) [1] insert#1(nil, @x) -> ::(@x, nil) [1] insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) [1] insertD(@x, @l) -> insertD#1(@l, @x) [1] insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) [1] insertD#1(nil, @x) -> ::(@x, nil) [1] insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) [1] insertionsort(@l) -> insertionsort#1(@l) [1] insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) [1] insertionsort#1(nil) -> nil [1] insertionsortD(@l) -> insertionsortD#1(@l) [1] insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) [1] insertionsortD#1(nil) -> nil [1] testInsertionsort(@x) -> insertionsort(testList(#unit)) [1] testInsertionsortD(@x) -> insertionsortD(testList(#unit)) [1] testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) [1] #cklt(#EQ) -> #false [0] #cklt(#GT) -> #false [0] #cklt(#LT) -> #true [0] #compare(#0, #0) -> #EQ [0] #compare(#0, #neg(@y)) -> #GT [0] #compare(#0, #pos(@y)) -> #LT [0] #compare(#0, #s(@y)) -> #LT [0] #compare(#neg(@x), #0) -> #LT [0] #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] #compare(#neg(@x), #pos(@y)) -> #LT [0] #compare(#pos(@x), #0) -> #GT [0] #compare(#pos(@x), #neg(@y)) -> #GT [0] #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] #compare(#s(@x), #0) -> #GT [0] #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] The TRS has the following type information: #abs :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #0 :: #0:#neg:#pos:#s #neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true #cklt :: #EQ:#GT:#LT -> #false:#true #compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT insert :: #0:#neg:#pos:#s -> :::nil -> :::nil insert#1 :: :::nil -> #0:#neg:#pos:#s -> :::nil :: :: #0:#neg:#pos:#s -> :::nil -> :::nil insert#2 :: #false:#true -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> :::nil -> :::nil nil :: :::nil #false :: #false:#true #true :: #false:#true insertD :: #0:#neg:#pos:#s -> :::nil -> :::nil insertD#1 :: :::nil -> #0:#neg:#pos:#s -> :::nil insertD#2 :: #false:#true -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> :::nil -> :::nil insertionsort :: :::nil -> :::nil insertionsort#1 :: :::nil -> :::nil insertionsortD :: :::nil -> :::nil insertionsortD#1 :: :::nil -> :::nil testInsertionsort :: a -> :::nil testList :: #unit -> :::nil #unit :: #unit testInsertionsortD :: b -> :::nil #EQ :: #EQ:#GT:#LT #GT :: #EQ:#GT:#LT #LT :: #EQ:#GT:#LT Rewrite Strategy: INNERMOST ---------------------------------------- (7) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: #cklt(v0) -> null_#cklt [0] #compare(v0, v1) -> null_#compare [0] insert#2(v0, v1, v2, v3) -> null_insert#2 [0] insertD#2(v0, v1, v2, v3) -> null_insertD#2 [0] insert#1(v0, v1) -> null_insert#1 [0] insertD#1(v0, v1) -> null_insertD#1 [0] insertionsort#1(v0) -> null_insertionsort#1 [0] insertionsortD#1(v0) -> null_insertionsortD#1 [0] And the following fresh constants: null_#cklt, null_#compare, null_insert#2, null_insertD#2, null_insert#1, null_insertD#1, null_insertionsort#1, null_insertionsortD#1, const, const1 ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: #abs(#0) -> #0 [1] #abs(#neg(@x)) -> #pos(@x) [1] #abs(#pos(@x)) -> #pos(@x) [1] #abs(#s(@x)) -> #pos(#s(@x)) [1] #less(@x, @y) -> #cklt(#compare(@x, @y)) [1] insert(@x, @l) -> insert#1(@l, @x) [1] insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) [1] insert#1(nil, @x) -> ::(@x, nil) [1] insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) [1] insertD(@x, @l) -> insertD#1(@l, @x) [1] insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) [1] insertD#1(nil, @x) -> ::(@x, nil) [1] insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) [1] insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) [1] insertionsort(@l) -> insertionsort#1(@l) [1] insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) [1] insertionsort#1(nil) -> nil [1] insertionsortD(@l) -> insertionsortD#1(@l) [1] insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) [1] insertionsortD#1(nil) -> nil [1] testInsertionsort(@x) -> insertionsort(testList(#unit)) [1] testInsertionsortD(@x) -> insertionsortD(testList(#unit)) [1] testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) [1] #cklt(#EQ) -> #false [0] #cklt(#GT) -> #false [0] #cklt(#LT) -> #true [0] #compare(#0, #0) -> #EQ [0] #compare(#0, #neg(@y)) -> #GT [0] #compare(#0, #pos(@y)) -> #LT [0] #compare(#0, #s(@y)) -> #LT [0] #compare(#neg(@x), #0) -> #LT [0] #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) [0] #compare(#neg(@x), #pos(@y)) -> #LT [0] #compare(#pos(@x), #0) -> #GT [0] #compare(#pos(@x), #neg(@y)) -> #GT [0] #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) [0] #compare(#s(@x), #0) -> #GT [0] #compare(#s(@x), #s(@y)) -> #compare(@x, @y) [0] #cklt(v0) -> null_#cklt [0] #compare(v0, v1) -> null_#compare [0] insert#2(v0, v1, v2, v3) -> null_insert#2 [0] insertD#2(v0, v1, v2, v3) -> null_insertD#2 [0] insert#1(v0, v1) -> null_insert#1 [0] insertD#1(v0, v1) -> null_insertD#1 [0] insertionsort#1(v0) -> null_insertionsort#1 [0] insertionsortD#1(v0) -> null_insertionsortD#1 [0] The TRS has the following type information: #abs :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #0 :: #0:#neg:#pos:#s #neg :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #pos :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #s :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s #less :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #false:#true:null_#cklt #cklt :: #EQ:#GT:#LT:null_#compare -> #false:#true:null_#cklt #compare :: #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> #EQ:#GT:#LT:null_#compare insert :: #0:#neg:#pos:#s -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insert#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> #0:#neg:#pos:#s -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 :: :: #0:#neg:#pos:#s -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insert#2 :: #false:#true:null_#cklt -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 nil :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 #false :: #false:#true:null_#cklt #true :: #false:#true:null_#cklt insertD :: #0:#neg:#pos:#s -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insertD#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> #0:#neg:#pos:#s -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insertD#2 :: #false:#true:null_#cklt -> #0:#neg:#pos:#s -> #0:#neg:#pos:#s -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insertionsort :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insertionsort#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insertionsortD :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 insertionsortD#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 testInsertionsort :: a -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 testList :: #unit -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 #unit :: #unit testInsertionsortD :: b -> :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 #EQ :: #EQ:#GT:#LT:null_#compare #GT :: #EQ:#GT:#LT:null_#compare #LT :: #EQ:#GT:#LT:null_#compare null_#cklt :: #false:#true:null_#cklt null_#compare :: #EQ:#GT:#LT:null_#compare null_insert#2 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 null_insertD#2 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 null_insert#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 null_insertD#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 null_insertionsort#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 null_insertionsortD#1 :: :::nil:null_insert#2:null_insertD#2:null_insert#1:null_insertD#1:null_insertionsort#1:null_insertionsortD#1 const :: a const1 :: b Rewrite Strategy: INNERMOST ---------------------------------------- (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: #0 => 0 nil => 0 #false => 1 #true => 2 #unit => 0 #EQ => 1 #GT => 2 #LT => 3 null_#cklt => 0 null_#compare => 0 null_insert#2 => 0 null_insertD#2 => 0 null_insert#1 => 0 null_insertD#1 => 0 null_insertionsort#1 => 0 null_insertionsortD#1 => 0 const => 0 const1 => 0 ---------------------------------------- (10) Obligation: Complexity RNTS consisting of the following rules: #abs(z) -{ 1 }-> 0 :|: z = 0 #abs(z) -{ 1 }-> 1 + @x :|: @x >= 0, z = 1 + @x #abs(z) -{ 1 }-> 1 + (1 + @x) :|: @x >= 0, z = 1 + @x #cklt(z) -{ 0 }-> 2 :|: z = 3 #cklt(z) -{ 0 }-> 1 :|: z = 1 #cklt(z) -{ 0 }-> 1 :|: z = 2 #cklt(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 #compare(z, z') -{ 0 }-> 3 :|: z = 0, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 0 #compare(z, z') -{ 0 }-> 3 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 2 :|: z = 0, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 0 #compare(z, z') -{ 0 }-> 2 :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> 1 :|: z = 0, z' = 0 #compare(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 #compare(z, z') -{ 0 }-> #compare(@x, @y) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #compare(z, z') -{ 0 }-> #compare(@y, @x) :|: @x >= 0, z = 1 + @x, z' = 1 + @y, @y >= 0 #less(z, z') -{ 1 }-> #cklt(#compare(@x, @y)) :|: z = @x, @x >= 0, z' = @y, @y >= 0 insert(z, z') -{ 1 }-> insert#1(@l, @x) :|: z = @x, @l >= 0, @x >= 0, z' = @l insert#1(z, z') -{ 1 }-> insert#2(#less(@y, @x), @x, @y, @ys) :|: z = 1 + @y + @ys, @x >= 0, @y >= 0, z' = @x, @ys >= 0 insert#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 insert#1(z, z') -{ 1 }-> 1 + @x + 0 :|: @x >= 0, z = 0, z' = @x insert#2(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 insert#2(z, z', z'', z1) -{ 1 }-> 1 + @x + (1 + @y + @ys) :|: @x >= 0, z = 1, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y insert#2(z, z', z'', z1) -{ 1 }-> 1 + @y + insert(@x, @ys) :|: z = 2, @x >= 0, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y insertD(z, z') -{ 1 }-> insertD#1(@l, @x) :|: z = @x, @l >= 0, @x >= 0, z' = @l insertD#1(z, z') -{ 1 }-> insertD#2(#less(@y, @x), @x, @y, @ys) :|: z = 1 + @y + @ys, @x >= 0, @y >= 0, z' = @x, @ys >= 0 insertD#1(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 insertD#1(z, z') -{ 1 }-> 1 + @x + 0 :|: @x >= 0, z = 0, z' = @x insertD#2(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 insertD#2(z, z', z'', z1) -{ 1 }-> 1 + @x + (1 + @y + @ys) :|: @x >= 0, z = 1, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y insertD#2(z, z', z'', z1) -{ 1 }-> 1 + @y + insertD(@x, @ys) :|: z = 2, @x >= 0, z1 = @ys, @y >= 0, z' = @x, @ys >= 0, z'' = @y insertionsort(z) -{ 1 }-> insertionsort#1(@l) :|: z = @l, @l >= 0 insertionsort#1(z) -{ 1 }-> insert(@x, insertionsort(@xs)) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 insertionsort#1(z) -{ 1 }-> 0 :|: z = 0 insertionsort#1(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 insertionsortD(z) -{ 1 }-> insertionsortD#1(@l) :|: z = @l, @l >= 0 insertionsortD#1(z) -{ 1 }-> insertD(@x, insertionsortD(@xs)) :|: @x >= 0, z = 1 + @x + @xs, @xs >= 0 insertionsortD#1(z) -{ 1 }-> 0 :|: z = 0 insertionsortD#1(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 testInsertionsort(z) -{ 1 }-> insertionsort(testList(0)) :|: z = @x, @x >= 0 testInsertionsortD(z) -{ 1 }-> insertionsortD(testList(0)) :|: z = @x, @x >= 0 testList(z) -{ 1 }-> 1 + #abs(0) + (1 + #abs(1 + (1 + (1 + (1 + (1 + 0))))) + (1 + #abs(1 + (1 + (1 + (1 + (1 + (1 + 0)))))) + (1 + #abs(1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 0)))))))))) + (1 + #abs(1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 0)))))))) + (1 + #abs(1 + (1 + 0)) + (1 + #abs(1 + (1 + (1 + 0))) + (1 + #abs(1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 0))))))))) + (1 + #abs(1 + (1 + (1 + (1 + (1 + (1 + (1 + 0))))))) + (1 + #abs(1 + (1 + (1 + (1 + 0)))) + 0))))))))) :|: @_ >= 0, z = @_ Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (11) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V, V3, V13, V15),0,[fun(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[fun1(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V13, V15),0,[insert(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V13, V15),0,[fun4(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V13, V15),0,[fun5(V, V3, V13, V15, Out)],[V >= 0,V3 >= 0,V13 >= 0,V15 >= 0]). eq(start(V, V3, V13, V15),0,[insertD(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V13, V15),0,[fun6(V, V3, Out)],[V >= 0,V3 >= 0]). eq(start(V, V3, V13, V15),0,[fun7(V, V3, V13, V15, Out)],[V >= 0,V3 >= 0,V13 >= 0,V15 >= 0]). eq(start(V, V3, V13, V15),0,[insertionsort(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[fun8(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[insertionsortD(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[fun9(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[testInsertionsort(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[testInsertionsortD(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[testList(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[fun2(V, Out)],[V >= 0]). eq(start(V, V3, V13, V15),0,[fun3(V, V3, Out)],[V >= 0,V3 >= 0]). eq(fun(V, Out),1,[],[Out = 0,V = 0]). eq(fun(V, Out),1,[],[Out = 1 + V1,V1 >= 0,V = 1 + V1]). eq(fun(V, Out),1,[],[Out = 2 + V2,V2 >= 0,V = 1 + V2]). eq(fun1(V, V3, Out),1,[fun3(V4, V5, Ret0),fun2(Ret0, Ret)],[Out = Ret,V = V4,V4 >= 0,V3 = V5,V5 >= 0]). eq(insert(V, V3, Out),1,[fun4(V7, V6, Ret1)],[Out = Ret1,V = V6,V7 >= 0,V6 >= 0,V3 = V7]). eq(fun4(V, V3, Out),1,[fun1(V9, V8, Ret01),fun5(Ret01, V8, V9, V10, Ret2)],[Out = Ret2,V = 1 + V10 + V9,V8 >= 0,V9 >= 0,V3 = V8,V10 >= 0]). eq(fun4(V, V3, Out),1,[],[Out = 1 + V11,V11 >= 0,V = 0,V3 = V11]). eq(fun5(V, V3, V13, V15, Out),1,[],[Out = 2 + V12 + V14 + V16,V14 >= 0,V = 1,V15 = V16,V12 >= 0,V3 = V14,V16 >= 0,V13 = V12]). eq(fun5(V, V3, V13, V15, Out),1,[insert(V18, V19, Ret11)],[Out = 1 + Ret11 + V17,V = 2,V18 >= 0,V15 = V19,V17 >= 0,V3 = V18,V19 >= 0,V13 = V17]). eq(insertD(V, V3, Out),1,[fun6(V21, V20, Ret3)],[Out = Ret3,V = V20,V21 >= 0,V20 >= 0,V3 = V21]). eq(fun6(V, V3, Out),1,[fun1(V22, V24, Ret02),fun7(Ret02, V24, V22, V23, Ret4)],[Out = Ret4,V = 1 + V22 + V23,V24 >= 0,V22 >= 0,V3 = V24,V23 >= 0]). eq(fun6(V, V3, Out),1,[],[Out = 1 + V25,V25 >= 0,V = 0,V3 = V25]). eq(fun7(V, V3, V13, V15, Out),1,[],[Out = 2 + V26 + V27 + V28,V28 >= 0,V = 1,V15 = V27,V26 >= 0,V3 = V28,V27 >= 0,V13 = V26]). eq(fun7(V, V3, V13, V15, Out),1,[insertD(V29, V30, Ret12)],[Out = 1 + Ret12 + V31,V = 2,V29 >= 0,V15 = V30,V31 >= 0,V3 = V29,V30 >= 0,V13 = V31]). eq(insertionsort(V, Out),1,[fun8(V32, Ret5)],[Out = Ret5,V = V32,V32 >= 0]). eq(fun8(V, Out),1,[insertionsort(V34, Ret13),insert(V33, Ret13, Ret6)],[Out = Ret6,V33 >= 0,V = 1 + V33 + V34,V34 >= 0]). eq(fun8(V, Out),1,[],[Out = 0,V = 0]). eq(insertionsortD(V, Out),1,[fun9(V35, Ret7)],[Out = Ret7,V = V35,V35 >= 0]). eq(fun9(V, Out),1,[insertionsortD(V37, Ret14),insertD(V36, Ret14, Ret8)],[Out = Ret8,V36 >= 0,V = 1 + V36 + V37,V37 >= 0]). eq(fun9(V, Out),1,[],[Out = 0,V = 0]). eq(testInsertionsort(V, Out),1,[testList(0, Ret03),insertionsort(Ret03, Ret9)],[Out = Ret9,V = V38,V38 >= 0]). eq(testInsertionsortD(V, Out),1,[testList(0, Ret04),insertionsortD(Ret04, Ret10)],[Out = Ret10,V = V39,V39 >= 0]). eq(testList(V, Out),1,[fun(0, Ret011),fun(1 + (1 + (1 + (1 + (1 + 0)))), Ret101),fun(1 + (1 + (1 + (1 + (1 + (1 + 0))))), Ret1101),fun(1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 0))))))))), Ret11101),fun(1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 0))))))), Ret111101),fun(1 + (1 + 0), Ret1111101),fun(1 + (1 + (1 + 0)), Ret11111101),fun(1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 0)))))))), Ret111111101),fun(1 + (1 + (1 + (1 + (1 + (1 + (1 + 0)))))), Ret1111111101),fun(1 + (1 + (1 + (1 + 0))), Ret11111111101)],[Out = 10 + Ret011 + Ret101 + Ret1101 + Ret11101 + Ret111101 + Ret1111101 + Ret11111101 + Ret111111101 + Ret1111111101 + Ret11111111101,V40 >= 0,V = V40]). eq(fun2(V, Out),0,[],[Out = 1,V = 1]). eq(fun2(V, Out),0,[],[Out = 1,V = 2]). eq(fun2(V, Out),0,[],[Out = 2,V = 3]). eq(fun3(V, V3, Out),0,[],[Out = 1,V = 0,V3 = 0]). eq(fun3(V, V3, Out),0,[],[Out = 2,V = 0,V3 = 1 + V41,V41 >= 0]). eq(fun3(V, V3, Out),0,[],[Out = 3,V = 0,V3 = 1 + V42,V42 >= 0]). eq(fun3(V, V3, Out),0,[],[Out = 3,V43 >= 0,V = 1 + V43,V3 = 0]). eq(fun3(V, V3, Out),0,[fun3(V45, V44, Ret15)],[Out = Ret15,V44 >= 0,V = 1 + V44,V3 = 1 + V45,V45 >= 0]). eq(fun3(V, V3, Out),0,[],[Out = 3,V46 >= 0,V = 1 + V46,V3 = 1 + V47,V47 >= 0]). eq(fun3(V, V3, Out),0,[],[Out = 2,V48 >= 0,V = 1 + V48,V3 = 0]). eq(fun3(V, V3, Out),0,[],[Out = 2,V50 >= 0,V = 1 + V50,V3 = 1 + V49,V49 >= 0]). eq(fun3(V, V3, Out),0,[fun3(V52, V51, Ret16)],[Out = Ret16,V52 >= 0,V = 1 + V52,V3 = 1 + V51,V51 >= 0]). eq(fun2(V, Out),0,[],[Out = 0,V53 >= 0,V = V53]). eq(fun3(V, V3, Out),0,[],[Out = 0,V55 >= 0,V54 >= 0,V = V55,V3 = V54]). eq(fun5(V, V3, V13, V15, Out),0,[],[Out = 0,V15 = V58,V57 >= 0,V13 = V59,V56 >= 0,V = V57,V3 = V56,V59 >= 0,V58 >= 0]). eq(fun7(V, V3, V13, V15, Out),0,[],[Out = 0,V15 = V63,V60 >= 0,V13 = V61,V62 >= 0,V = V60,V3 = V62,V61 >= 0,V63 >= 0]). eq(fun4(V, V3, Out),0,[],[Out = 0,V64 >= 0,V65 >= 0,V = V64,V3 = V65]). eq(fun6(V, V3, Out),0,[],[Out = 0,V67 >= 0,V66 >= 0,V = V67,V3 = V66]). eq(fun8(V, Out),0,[],[Out = 0,V68 >= 0,V = V68]). eq(fun9(V, Out),0,[],[Out = 0,V69 >= 0,V = V69]). input_output_vars(fun(V,Out),[V],[Out]). input_output_vars(fun1(V,V3,Out),[V,V3],[Out]). input_output_vars(insert(V,V3,Out),[V,V3],[Out]). input_output_vars(fun4(V,V3,Out),[V,V3],[Out]). input_output_vars(fun5(V,V3,V13,V15,Out),[V,V3,V13,V15],[Out]). input_output_vars(insertD(V,V3,Out),[V,V3],[Out]). input_output_vars(fun6(V,V3,Out),[V,V3],[Out]). input_output_vars(fun7(V,V3,V13,V15,Out),[V,V3,V13,V15],[Out]). input_output_vars(insertionsort(V,Out),[V],[Out]). input_output_vars(fun8(V,Out),[V],[Out]). input_output_vars(insertionsortD(V,Out),[V],[Out]). input_output_vars(fun9(V,Out),[V],[Out]). input_output_vars(testInsertionsort(V,Out),[V],[Out]). input_output_vars(testInsertionsortD(V,Out),[V],[Out]). input_output_vars(testList(V,Out),[V],[Out]). input_output_vars(fun2(V,Out),[V],[Out]). input_output_vars(fun3(V,V3,Out),[V,V3],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [fun/2] 1. non_recursive : [fun2/2] 2. recursive : [fun3/3] 3. non_recursive : [fun1/3] 4. recursive : [fun4/3,fun5/5,insert/3] 5. recursive : [fun6/3,fun7/5,insertD/3] 6. recursive [non_tail] : [fun8/2,insertionsort/2] 7. recursive [non_tail] : [fun9/2,insertionsortD/2] 8. non_recursive : [testList/2] 9. non_recursive : [testInsertionsort/2] 10. non_recursive : [testInsertionsortD/2] 11. non_recursive : [start/4] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun/2 1. SCC is partially evaluated into fun2/2 2. SCC is partially evaluated into fun3/3 3. SCC is partially evaluated into fun1/3 4. SCC is partially evaluated into insert/3 5. SCC is partially evaluated into insertD/3 6. SCC is partially evaluated into insertionsort/2 7. SCC is partially evaluated into insertionsortD/2 8. SCC is partially evaluated into testList/2 9. SCC is partially evaluated into testInsertionsort/2 10. SCC is partially evaluated into testInsertionsortD/2 11. SCC is partially evaluated into start/4 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun/2 * CE 41 is refined into CE [60] * CE 42 is refined into CE [61] * CE 40 is refined into CE [62] ### Cost equations --> "Loop" of fun/2 * CEs [60] --> Loop 37 * CEs [61] --> Loop 38 * CEs [62] --> Loop 39 ### Ranking functions of CR fun(V,Out) #### Partial ranking functions of CR fun(V,Out) ### Specialization of cost equations fun2/2 * CE 49 is refined into CE [63] * CE 48 is refined into CE [64] * CE 47 is refined into CE [65] * CE 46 is refined into CE [66] ### Cost equations --> "Loop" of fun2/2 * CEs [63] --> Loop 40 * CEs [64] --> Loop 41 * CEs [65] --> Loop 42 * CEs [66] --> Loop 43 ### Ranking functions of CR fun2(V,Out) #### Partial ranking functions of CR fun2(V,Out) ### Specialization of cost equations fun3/3 * CE 55 is refined into CE [67] * CE 57 is refined into CE [68] * CE 59 is refined into CE [69] * CE 53 is refined into CE [70] * CE 56 is refined into CE [71] * CE 52 is refined into CE [72] * CE 51 is refined into CE [73] * CE 50 is refined into CE [74] * CE 54 is refined into CE [75] * CE 58 is refined into CE [76] ### Cost equations --> "Loop" of fun3/3 * CEs [75] --> Loop 44 * CEs [76] --> Loop 45 * CEs [67] --> Loop 46 * CEs [68] --> Loop 47 * CEs [69] --> Loop 48 * CEs [70] --> Loop 49 * CEs [71] --> Loop 50 * CEs [72] --> Loop 51 * CEs [73] --> Loop 52 * CEs [74] --> Loop 53 ### Ranking functions of CR fun3(V,V3,Out) * RF of phase [44,45]: [V/2+V3/2-1/2] #### Partial ranking functions of CR fun3(V,V3,Out) * Partial RF of phase [44,45]: - RF of loop [44:1]: V/2+V3/2-1/2 - RF of loop [45:1]: V depends on loops [44:1] V3 depends on loops [44:1] ### Specialization of cost equations fun1/3 * CE 39 is refined into CE [77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93] ### Cost equations --> "Loop" of fun1/3 * CEs [92] --> Loop 54 * CEs [88,90] --> Loop 55 * CEs [89] --> Loop 56 * CEs [85] --> Loop 57 * CEs [83] --> Loop 58 * CEs [84,86] --> Loop 59 * CEs [81] --> Loop 60 * CEs [79] --> Loop 61 * CEs [80,82] --> Loop 62 * CEs [77] --> Loop 63 * CEs [78,87,91,93] --> Loop 64 ### Ranking functions of CR fun1(V,V3,Out) #### Partial ranking functions of CR fun1(V,V3,Out) ### Specialization of cost equations insert/3 * CE 36 is refined into CE [94,95,96,97] * CE 34 is refined into CE [98,99,100,101,102,103,104,105,106,107] * CE 37 is refined into CE [108] * CE 38 is refined into CE [109] * CE 35 is refined into CE [110,111,112] ### Cost equations --> "Loop" of insert/3 * CEs [112] --> Loop 65 * CEs [110] --> Loop 66 * CEs [111] --> Loop 67 * CEs [95,97] --> Loop 68 * CEs [109] --> Loop 69 * CEs [94,96] --> Loop 70 * CEs [98,99,100,101,102,103,104,105,106,107,108] --> Loop 71 ### Ranking functions of CR insert(V,V3,Out) * RF of phase [65,66]: [V3] * RF of phase [67]: [V3-1] #### Partial ranking functions of CR insert(V,V3,Out) * Partial RF of phase [65,66]: - RF of loop [65:1]: V3/2-1/2 - RF of loop [66:1]: V3 * Partial RF of phase [67]: - RF of loop [67:1]: V3-1 ### Specialization of cost equations insertD/3 * CE 28 is refined into CE [113,114,115,116] * CE 26 is refined into CE [117,118,119,120,121,122,123,124,125,126] * CE 29 is refined into CE [127] * CE 30 is refined into CE [128] * CE 27 is refined into CE [129,130,131] ### Cost equations --> "Loop" of insertD/3 * CEs [131] --> Loop 72 * CEs [129] --> Loop 73 * CEs [130] --> Loop 74 * CEs [114,116] --> Loop 75 * CEs [128] --> Loop 76 * CEs [113,115] --> Loop 77 * CEs [117,118,119,120,121,122,123,124,125,126,127] --> Loop 78 ### Ranking functions of CR insertD(V,V3,Out) * RF of phase [72,73]: [V3] * RF of phase [74]: [V3-1] #### Partial ranking functions of CR insertD(V,V3,Out) * Partial RF of phase [72,73]: - RF of loop [72:1]: V3/2-1/2 - RF of loop [73:1]: V3 * Partial RF of phase [74]: - RF of loop [74:1]: V3-1 ### Specialization of cost equations insertionsort/2 * CE 33 is refined into CE [132,133,134,135,136,137] * CE 31 is refined into CE [138] * CE 32 is refined into CE [139] ### Cost equations --> "Loop" of insertionsort/2 * CEs [138,139] --> Loop 79 * CEs [137] --> Loop 80 * CEs [136] --> Loop 81 * CEs [133] --> Loop 82 * CEs [132] --> Loop 83 * CEs [134] --> Loop 84 * CEs [135] --> Loop 85 ### Ranking functions of CR insertionsort(V,Out) * RF of phase [80,81,82,83,84,85]: [V] #### Partial ranking functions of CR insertionsort(V,Out) * Partial RF of phase [80,81,82,83,84,85]: - RF of loop [80:1,81:1]: V-1 - RF of loop [82:1,83:1,84:1,85:1]: V ### Specialization of cost equations insertionsortD/2 * CE 25 is refined into CE [140,141,142,143,144,145] * CE 23 is refined into CE [146] * CE 24 is refined into CE [147] ### Cost equations --> "Loop" of insertionsortD/2 * CEs [146,147] --> Loop 86 * CEs [145] --> Loop 87 * CEs [144] --> Loop 88 * CEs [141] --> Loop 89 * CEs [140] --> Loop 90 * CEs [142] --> Loop 91 * CEs [143] --> Loop 92 ### Ranking functions of CR insertionsortD(V,Out) * RF of phase [87,88,89,90,91,92]: [V] #### Partial ranking functions of CR insertionsortD(V,Out) * Partial RF of phase [87,88,89,90,91,92]: - RF of loop [87:1,88:1]: V-1 - RF of loop [89:1,90:1,91:1,92:1]: V ### Specialization of cost equations testList/2 * CE 45 is refined into CE [148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659] ### Cost equations --> "Loop" of testList/2 * CEs [148] --> Loop 93 * CEs [149,150,152,156,164,180,212,276,404] --> Loop 94 * CEs [151,153,154,157,158,160,165,166,168,172,181,182,184,188,196,213,214,216,220,228,244,277,278,280,284,292,308,340,405,406,408,412,420,436,468,532] --> Loop 95 * CEs [155,159,161,162,167,169,170,173,174,176,183,185,186,189,190,192,197,198,200,204,215,217,218,221,222,224,229,230,232,236,245,246,248,252,260,279,281,282,285,286,288,293,294,296,300,309,310,312,316,324,341,342,344,348,356,372,407,409,410,413,414,416,421,422,424,428,437,438,440,444,452,469,470,472,476,484,500,533,534,536,540,548,564,596] --> Loop 96 * CEs [163,171,175,177,178,187,191,193,194,199,201,202,205,206,208,219,223,225,226,231,233,234,237,238,240,247,249,250,253,254,256,261,262,264,268,283,287,289,290,295,297,298,301,302,304,311,313,314,317,318,320,325,326,328,332,343,345,346,349,350,352,357,358,360,364,373,374,376,380,388,411,415,417,418,423,425,426,429,430,432,439,441,442,445,446,448,453,454,456,460,471,473,474,477,478,480,485,486,488,492,501,502,504,508,516,535,537,538,541,542,544,549,550,552,556,565,566,568,572,580,597,598,600,604,612,628] --> Loop 97 * CEs [179,195,203,207,209,210,227,235,239,241,242,251,255,257,258,263,265,266,269,270,272,291,299,303,305,306,315,319,321,322,327,329,330,333,334,336,347,351,353,354,359,361,362,365,366,368,375,377,378,381,382,384,389,390,392,396,419,427,431,433,434,443,447,449,450,455,457,458,461,462,464,475,479,481,482,487,489,490,493,494,496,503,505,506,509,510,512,517,518,520,524,539,543,545,546,551,553,554,557,558,560,567,569,570,573,574,576,581,582,584,588,599,601,602,605,606,608,613,614,616,620,629,630,632,636,644] --> Loop 98 * CEs [211,243,259,267,271,273,274,307,323,331,335,337,338,355,363,367,369,370,379,383,385,386,391,393,394,397,398,400,435,451,459,463,465,466,483,491,495,497,498,507,511,513,514,519,521,522,525,526,528,547,555,559,561,562,571,575,577,578,583,585,586,589,590,592,603,607,609,610,615,617,618,621,622,624,631,633,634,637,638,640,645,646,648,652] --> Loop 99 * CEs [275,339,371,387,395,399,401,402,467,499,515,523,527,529,530,563,579,587,591,593,594,611,619,623,625,626,635,639,641,642,647,649,650,653,654,656] --> Loop 100 * CEs [403,531,595,627,643,651,655,657,658] --> Loop 101 * CEs [659] --> Loop 102 ### Ranking functions of CR testList(V,Out) #### Partial ranking functions of CR testList(V,Out) ### Specialization of cost equations testInsertionsort/2 * CE 43 is refined into CE [660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679] ### Cost equations --> "Loop" of testInsertionsort/2 * CEs [660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679] --> Loop 103 ### Ranking functions of CR testInsertionsort(V,Out) #### Partial ranking functions of CR testInsertionsort(V,Out) ### Specialization of cost equations testInsertionsortD/2 * CE 44 is refined into CE [680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699] ### Cost equations --> "Loop" of testInsertionsortD/2 * CEs [680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699] --> Loop 104 ### Ranking functions of CR testInsertionsortD(V,Out) #### Partial ranking functions of CR testInsertionsortD(V,Out) ### Specialization of cost equations start/4 * CE 7 is refined into CE [700,701,702,703,704,705] * CE 11 is refined into CE [706,707,708,709,710,711] * CE 9 is refined into CE [712] * CE 1 is refined into CE [713] * CE 2 is refined into CE [714] * CE 3 is refined into CE [715,716,717,718,719,720,721,722] * CE 4 is refined into CE [723,724,725,726,727,728,729,730] * CE 5 is refined into CE [731,732,733,734,735,736,737,738,739,740] * CE 6 is refined into CE [741,742,743,744,745,746,747,748,749,750,751,752] * CE 8 is refined into CE [753,754,755,756] * CE 10 is refined into CE [757,758,759,760,761,762,763,764,765,766,767,768] * CE 12 is refined into CE [769,770,771] * CE 13 is refined into CE [772,773,774,775,776,777,778,779,780,781] * CE 14 is refined into CE [782,783,784,785,786,787] * CE 15 is refined into CE [788,789,790,791,792,793] * CE 16 is refined into CE [794,795] * CE 17 is refined into CE [796,797] * CE 18 is refined into CE [798] * CE 19 is refined into CE [799] * CE 20 is refined into CE [800,801,802,803,804,805,806,807,808,809] * CE 21 is refined into CE [810,811,812,813] * CE 22 is refined into CE [814,815,816,817,818,819,820,821,822] ### Cost equations --> "Loop" of start/4 * CEs [779,820] --> Loop 105 * CEs [731,735,736,737,745,746,747,748,753,755,761,762,763,764,776,777,778,784,790,817,818] --> Loop 106 * CEs [812] --> Loop 107 * CEs [700,701,702,703,704,705,706,707,708,709,710,711,811] --> Loop 108 * CEs [712,741,757,810] --> Loop 109 * CEs [713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,732,733,734,738,739,740,742,743,744,749,750,751,752,754,756,758,759,760,765,766,767,768,769,770,771,772,773,774,775,780,781,782,783,785,786,787,788,789,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,813,814,815,816,819,821,822] --> Loop 110 ### Ranking functions of CR start(V,V3,V13,V15) #### Partial ranking functions of CR start(V,V3,V13,V15) Computing Bounds ===================================== #### Cost of chains of fun(V,Out): * Chain [39]: 1 with precondition: [V=0,Out=0] * Chain [38]: 1 with precondition: [V+1=Out,V>=1] * Chain [37]: 1 with precondition: [V=Out,V>=1] #### Cost of chains of fun2(V,Out): * Chain [43]: 0 with precondition: [V=1,Out=1] * Chain [42]: 0 with precondition: [V=2,Out=1] * Chain [41]: 0 with precondition: [V=3,Out=2] * Chain [40]: 0 with precondition: [Out=0,V>=0] #### Cost of chains of fun3(V,V3,Out): * Chain [[44,45],53]: 0 with precondition: [Out=1,V3=V,V3>=1] * Chain [[44,45],52]: 0 with precondition: [Out=2,V>=1,V3>=1,V+V3>=3] * Chain [[44,45],51]: 0 with precondition: [Out=3,V>=1,V3>=1,V+V3>=3] * Chain [[44,45],50]: 0 with precondition: [Out=2,V>=1,V3>=1,V+V3>=3] * Chain [[44,45],49]: 0 with precondition: [Out=3,V>=1,V3>=1,V+V3>=3] * Chain [[44,45],48]: 0 with precondition: [Out=0,V>=1,V3>=1] * Chain [[44,45],47]: 0 with precondition: [Out=2,V>=2,V3>=2] * Chain [[44,45],46]: 0 with precondition: [Out=3,V>=2,V3>=2] * Chain [53]: 0 with precondition: [V=0,V3=0,Out=1] * Chain [52]: 0 with precondition: [V=0,Out=2,V3>=1] * Chain [51]: 0 with precondition: [V=0,Out=3,V3>=1] * Chain [50]: 0 with precondition: [V3=0,Out=2,V>=1] * Chain [49]: 0 with precondition: [V3=0,Out=3,V>=1] * Chain [48]: 0 with precondition: [Out=0,V>=0,V3>=0] * Chain [47]: 0 with precondition: [Out=2,V>=1,V3>=1] * Chain [46]: 0 with precondition: [Out=3,V>=1,V3>=1] #### Cost of chains of fun1(V,V3,Out): * Chain [64]: 1 with precondition: [Out=0,V>=0,V3>=0] * Chain [63]: 1 with precondition: [V=0,V3=0,Out=1] * Chain [62]: 1 with precondition: [V=0,Out=0,V3>=1] * Chain [61]: 1 with precondition: [V=0,Out=1,V3>=1] * Chain [60]: 1 with precondition: [V=0,Out=2,V3>=1] * Chain [59]: 1 with precondition: [V3=0,Out=0,V>=1] * Chain [58]: 1 with precondition: [V3=0,Out=1,V>=1] * Chain [57]: 1 with precondition: [V3=0,Out=2,V>=1] * Chain [56]: 1 with precondition: [Out=0,V=V3,V>=1] * Chain [55]: 1 with precondition: [Out=1,V>=1,V3>=1] * Chain [54]: 1 with precondition: [Out=2,V>=1,V3>=1] #### Cost of chains of insert(V,V3,Out): * Chain [[67],71]: 4*it(67)+3 Such that:it(67) =< Out with precondition: [V=0,Out>=2,V3>=Out] * Chain [[67],70]: 4*it(67)+4 Such that:it(67) =< Out with precondition: [V=0,V3+1=Out,V3>=3] * Chain [[67],69]: 4*it(67)+2 Such that:it(67) =< Out with precondition: [V=0,V3+1=Out,V3>=2] * Chain [[65,66],71]: 4*it(65)+4*it(66)+3 Such that:aux(16) =< V3 aux(17) =< Out it(65) =< Out/2 it(65) =< aux(16) it(66) =< aux(16) it(65) =< aux(17) it(66) =< aux(17) with precondition: [V>=1,Out>=1,V3>=Out] * Chain [[65,66],69]: 4*it(65)+4*it(66)+2 Such that:it(65) =< -V/2+Out/2 aux(18) =< -V+Out it(65) =< aux(18) it(66) =< aux(18) with precondition: [V+V3+1=Out,V>=1,V3>=1] * Chain [[65,66],68]: 4*it(65)+4*it(66)+4 Such that:it(65) =< -V/2+Out/2 aux(19) =< -V+Out it(65) =< aux(19) it(66) =< aux(19) with precondition: [V+V3+1=Out,V>=1,V3>=2] * Chain [71]: 3 with precondition: [Out=0,V>=0,V3>=0] * Chain [70]: 4 with precondition: [V=0,V3+1=Out,V3>=1] * Chain [69]: 2 with precondition: [V3=0,V+1=Out,V>=0] * Chain [68]: 4 with precondition: [V+V3+1=Out,V>=1,V3>=1] #### Cost of chains of insertD(V,V3,Out): * Chain [[74],78]: 4*it(74)+3 Such that:it(74) =< Out with precondition: [V=0,Out>=2,V3>=Out] * Chain [[74],77]: 4*it(74)+4 Such that:it(74) =< Out with precondition: [V=0,V3+1=Out,V3>=3] * Chain [[74],76]: 4*it(74)+2 Such that:it(74) =< Out with precondition: [V=0,V3+1=Out,V3>=2] * Chain [[72,73],78]: 4*it(72)+4*it(73)+3 Such that:aux(23) =< V3 aux(24) =< Out it(72) =< Out/2 it(72) =< aux(23) it(73) =< aux(23) it(72) =< aux(24) it(73) =< aux(24) with precondition: [V>=1,Out>=1,V3>=Out] * Chain [[72,73],76]: 4*it(72)+4*it(73)+2 Such that:it(72) =< -V/2+Out/2 aux(25) =< -V+Out it(72) =< aux(25) it(73) =< aux(25) with precondition: [V+V3+1=Out,V>=1,V3>=1] * Chain [[72,73],75]: 4*it(72)+4*it(73)+4 Such that:it(72) =< -V/2+Out/2 aux(26) =< -V+Out it(72) =< aux(26) it(73) =< aux(26) with precondition: [V+V3+1=Out,V>=1,V3>=2] * Chain [78]: 3 with precondition: [Out=0,V>=0,V3>=0] * Chain [77]: 4 with precondition: [V=0,V3+1=Out,V3>=1] * Chain [76]: 2 with precondition: [V3=0,V+1=Out,V>=0] * Chain [75]: 4 with precondition: [V+V3+1=Out,V>=1,V3>=1] #### Cost of chains of insertionsort(V,Out): * Chain [[80,81,82,83,84,85],79]: 31*it(80)+4*s(38)+4*s(39)+8*s(41)+8*s(42)+4*s(45)+8*s(46)+2 Such that:aux(39) =< V it(80) =< aux(39) aux(36) =< aux(39)+2 aux(33) =< aux(39)+1 aux(32) =< it(80)*aux(39) s(47) =< it(80)*aux(36) s(45) =< it(80)*aux(33) aux(34) =< it(80)*aux(33) s(38) =< aux(32)*(1/2) s(44) =< aux(34)*(1/2) s(46) =< s(47) s(41) =< s(44) s(41) =< aux(34) s(42) =< aux(34) s(38) =< aux(32) s(39) =< aux(32) with precondition: [V>=1,Out>=0,V>=Out] * Chain [79]: 2 with precondition: [Out=0,V>=0] #### Cost of chains of insertionsortD(V,Out): * Chain [[87,88,89,90,91,92],86]: 31*it(87)+4*s(69)+4*s(70)+8*s(72)+8*s(73)+4*s(76)+8*s(77)+2 Such that:aux(49) =< V it(87) =< aux(49) aux(46) =< aux(49)+2 aux(43) =< aux(49)+1 aux(42) =< it(87)*aux(49) s(78) =< it(87)*aux(46) s(76) =< it(87)*aux(43) aux(44) =< it(87)*aux(43) s(69) =< aux(42)*(1/2) s(75) =< aux(44)*(1/2) s(77) =< s(78) s(72) =< s(75) s(72) =< aux(44) s(73) =< aux(44) s(69) =< aux(42) s(70) =< aux(42) with precondition: [V>=1,Out>=0,V>=Out] * Chain [86]: 2 with precondition: [Out=0,V>=0] #### Cost of chains of testList(V,Out): * Chain [102]: 11 with precondition: [Out=64,V>=0] * Chain [101]: 11 with precondition: [Out=65,V>=0] * Chain [100]: 11 with precondition: [Out=66,V>=0] * Chain [99]: 11 with precondition: [Out=67,V>=0] * Chain [98]: 11 with precondition: [Out=68,V>=0] * Chain [97]: 11 with precondition: [Out=69,V>=0] * Chain [96]: 11 with precondition: [Out=70,V>=0] * Chain [95]: 11 with precondition: [Out=71,V>=0] * Chain [94]: 11 with precondition: [Out=72,V>=0] * Chain [93]: 11 with precondition: [Out=73,V>=0] #### Cost of chains of testInsertionsort(V,Out): * Chain [103]: 1453319 with precondition: [73>=Out,V>=0,Out>=0] #### Cost of chains of testInsertionsortD(V,Out): * Chain [104]: 1453319 with precondition: [73>=Out,V>=0,Out>=0] #### Cost of chains of start(V,V3,V13,V15): * Chain [110]: 530*s(360)+56*s(365)+56*s(367)+112*s(369)+112*s(370)+112*s(371)+56*s(372)+72*s(434)+32*s(582)+16*s(583)+16*s(586)+8*s(590)+1453319 Such that:aux(64) =< V aux(65) =< V/2 aux(66) =< V3 aux(67) =< V3+1 aux(68) =< V3/2 aux(69) =< V3/2+1/2 s(434) =< aux(65) s(583) =< aux(66) s(590) =< aux(68) s(360) =< aux(64) s(361) =< aux(64)+2 s(362) =< aux(64)+1 s(363) =< s(360)*aux(64) s(364) =< s(360)*s(361) s(365) =< s(360)*s(362) s(366) =< s(360)*s(362) s(367) =< s(363)*(1/2) s(368) =< s(366)*(1/2) s(369) =< s(364) s(370) =< s(368) s(370) =< s(366) s(371) =< s(366) s(367) =< s(363) s(372) =< s(363) s(434) =< aux(64) s(582) =< aux(67) s(586) =< aux(69) s(586) =< aux(67) s(590) =< aux(66) with precondition: [V>=0] * Chain [109]: 5 with precondition: [V=1] * Chain [108]: 32*s(632)+16*s(633)+16*s(636)+8*s(640)+5 Such that:aux(72) =< V15 aux(73) =< V15+1 aux(74) =< V15/2 aux(75) =< V15/2+1/2 s(633) =< aux(72) s(640) =< aux(74) s(632) =< aux(73) s(636) =< aux(75) s(636) =< aux(73) s(640) =< aux(72) with precondition: [V=2] * Chain [107]: 0 with precondition: [V=3] * Chain [106]: 24*s(654)+7 Such that:aux(76) =< V s(654) =< aux(76) with precondition: [V3=0,V>=0] * Chain [105]: 1 with precondition: [V=V3,V>=1] Closed-form bounds of start(V,V3,V13,V15): ------------------------------------- * Chain [110] with precondition: [V>=0] - Upper bound: 978*V+1453319+420*V*V+nat(V3)*16+nat(V3+1)*32+nat(V3/2+1/2)*16+36*V+nat(V3/2)*8 - Complexity: n^2 * Chain [109] with precondition: [V=1] - Upper bound: 5 - Complexity: constant * Chain [108] with precondition: [V=2] - Upper bound: nat(V15)*16+5+nat(V15+1)*32+nat(V15/2+1/2)*16+nat(V15/2)*8 - Complexity: n * Chain [107] with precondition: [V=3] - Upper bound: 0 - Complexity: constant * Chain [106] with precondition: [V3=0,V>=0] - Upper bound: 24*V+7 - Complexity: n * Chain [105] with precondition: [V=V3,V>=1] - Upper bound: 1 - Complexity: constant ### Maximum cost of start(V,V3,V13,V15): max([max([5,nat(V15)*16+5+nat(V15+1)*32+nat(V15/2+1/2)*16+nat(V15/2)*8]),954*V+1453312+420*V*V+nat(V3)*16+nat(V3+1)*32+nat(V3/2+1/2)*16+36*V+nat(V3/2)*8+(24*V+7)]) Asymptotic class: n^2 * Total analysis performed in 5922 ms. ---------------------------------------- (12) BOUNDS(1, n^2) ---------------------------------------- (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (14) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #abs(#0) -> #0 #abs(#neg(@x)) -> #pos(@x) #abs(#pos(@x)) -> #pos(@x) #abs(#s(@x)) -> #pos(#s(@x)) #less(@x, @y) -> #cklt(#compare(@x, @y)) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insertD(@x, @l) -> insertD#1(@l, @x) insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) insertD#1(nil, @x) -> ::(@x, nil) insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) insertionsort(@l) -> insertionsort#1(@l) insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) insertionsort#1(nil) -> nil insertionsortD(@l) -> insertionsortD#1(@l) insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) insertionsortD#1(nil) -> nil testInsertionsort(@x) -> insertionsort(testList(#unit)) testInsertionsortD(@x) -> insertionsortD(testList(#unit)) testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) The (relative) TRS S consists of the following rules: #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) Rewrite Strategy: INNERMOST ---------------------------------------- (15) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence insertionsortD#1(::(@x, @xs)) ->^+ insertD(@x, insertionsortD#1(@xs)) gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. The pumping substitution is [@xs / ::(@x, @xs)]. The result substitution is [ ]. ---------------------------------------- (16) Complex Obligation (BEST) ---------------------------------------- (17) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #abs(#0) -> #0 #abs(#neg(@x)) -> #pos(@x) #abs(#pos(@x)) -> #pos(@x) #abs(#s(@x)) -> #pos(#s(@x)) #less(@x, @y) -> #cklt(#compare(@x, @y)) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insertD(@x, @l) -> insertD#1(@l, @x) insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) insertD#1(nil, @x) -> ::(@x, nil) insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) insertionsort(@l) -> insertionsort#1(@l) insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) insertionsort#1(nil) -> nil insertionsortD(@l) -> insertionsortD#1(@l) insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) insertionsortD#1(nil) -> nil testInsertionsort(@x) -> insertionsort(testList(#unit)) testInsertionsortD(@x) -> insertionsortD(testList(#unit)) testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) The (relative) TRS S consists of the following rules: #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) Rewrite Strategy: INNERMOST ---------------------------------------- (18) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (19) BOUNDS(n^1, INF) ---------------------------------------- (20) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: #abs(#0) -> #0 #abs(#neg(@x)) -> #pos(@x) #abs(#pos(@x)) -> #pos(@x) #abs(#s(@x)) -> #pos(#s(@x)) #less(@x, @y) -> #cklt(#compare(@x, @y)) insert(@x, @l) -> insert#1(@l, @x) insert#1(::(@y, @ys), @x) -> insert#2(#less(@y, @x), @x, @y, @ys) insert#1(nil, @x) -> ::(@x, nil) insert#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insert#2(#true, @x, @y, @ys) -> ::(@y, insert(@x, @ys)) insertD(@x, @l) -> insertD#1(@l, @x) insertD#1(::(@y, @ys), @x) -> insertD#2(#less(@y, @x), @x, @y, @ys) insertD#1(nil, @x) -> ::(@x, nil) insertD#2(#false, @x, @y, @ys) -> ::(@x, ::(@y, @ys)) insertD#2(#true, @x, @y, @ys) -> ::(@y, insertD(@x, @ys)) insertionsort(@l) -> insertionsort#1(@l) insertionsort#1(::(@x, @xs)) -> insert(@x, insertionsort(@xs)) insertionsort#1(nil) -> nil insertionsortD(@l) -> insertionsortD#1(@l) insertionsortD#1(::(@x, @xs)) -> insertD(@x, insertionsortD(@xs)) insertionsortD#1(nil) -> nil testInsertionsort(@x) -> insertionsort(testList(#unit)) testInsertionsortD(@x) -> insertionsortD(testList(#unit)) testList(@_) -> ::(#abs(#0), ::(#abs(#pos(#s(#s(#s(#s(#0)))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#0))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#s(#0))))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#0))))))))), ::(#abs(#pos(#s(#0))), ::(#abs(#pos(#s(#s(#0)))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#s(#s(#0)))))))))), ::(#abs(#pos(#s(#s(#s(#s(#s(#s(#0)))))))), ::(#abs(#pos(#s(#s(#s(#0))))), nil)))))))))) The (relative) TRS S consists of the following rules: #cklt(#EQ) -> #false #cklt(#GT) -> #false #cklt(#LT) -> #true #compare(#0, #0) -> #EQ #compare(#0, #neg(@y)) -> #GT #compare(#0, #pos(@y)) -> #LT #compare(#0, #s(@y)) -> #LT #compare(#neg(@x), #0) -> #LT #compare(#neg(@x), #neg(@y)) -> #compare(@y, @x) #compare(#neg(@x), #pos(@y)) -> #LT #compare(#pos(@x), #0) -> #GT #compare(#pos(@x), #neg(@y)) -> #GT #compare(#pos(@x), #pos(@y)) -> #compare(@x, @y) #compare(#s(@x), #0) -> #GT #compare(#s(@x), #s(@y)) -> #compare(@x, @y) Rewrite Strategy: INNERMOST