WORST_CASE(?,O(n^1)) * Step 1: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: cond_partition_pivot_heap_1(False(),x3,E(),x2,x1) -> Pair(E(),T(E(),x2,x1)) cond_partition_pivot_heap_1(False(),x6,T(x5,x4,x3),x2,x1) -> cond_partition_pivot_heap_7(leqElem#2(x4,x6) ,x6 ,x2 ,x1 ,x5 ,x4 ,x3) cond_partition_pivot_heap_1(True(),x3,x2,x1,E()) -> Pair(T(x2,x1,E()),E()) cond_partition_pivot_heap_1(True(),x6,x5,x4,T(x3,x2,x1)) -> cond_partition_pivot_heap_3(leqElem#2(x2,x6) ,x6 ,x5 ,x4 ,x3 ,x2 ,x1) cond_partition_pivot_heap_3(False(),x6,x5,x4,x3,x2,x1) -> cond_partition_pivot_heap_5(partition#2(x6,x3) ,x5 ,x4 ,x2 ,x1) cond_partition_pivot_heap_3(True(),x6,x5,x4,x3,x2,x1) -> cond_partition_pivot_heap_4(partition#2(x6,x1) ,x5 ,x4 ,x3 ,x2) cond_partition_pivot_heap_4(Pair(x12,x13),x6,x7,x9,x10) -> Pair(T(T(x6,x7,x9),x10,x12),x13) cond_partition_pivot_heap_5(Pair(x12,x13),x6,x7,x10,x11) -> Pair(T(x6,x7,x12),T(x13,x10,x11)) cond_partition_pivot_heap_7(False(),x6,x5,x4,x3,x2,x1) -> cond_partition_pivot_heap_9(partition#2(x6,x3) ,x5 ,x4 ,x2 ,x1) cond_partition_pivot_heap_7(True(),x6,x5,x4,x3,x2,x1) -> cond_partition_pivot_heap_8(partition#2(x6,x1) ,x5 ,x4 ,x3 ,x2) cond_partition_pivot_heap_8(Pair(x12,x13),x7,x8,x9,x10) -> Pair(T(x9,x10,x12),T(x13,x7,x8)) cond_partition_pivot_heap_9(Pair(x12,x13),x7,x8,x10,x11) -> Pair(x12,T(x13,x10,T(x11,x7,x8))) leq#2(0(),x12) -> True() leq#2(S(x16),0()) -> False() leq#2(S(x4),S(x2)) -> leq#2(x4,x2) leqElem#2(Elem(x4),Elem(x2)) -> leq#2(x4,x2) main(x2,x1) -> partition#2(x1,x2) partition#2(x2,E()) -> Pair(E(),E()) partition#2(x8,T(x6,x4,x2)) -> cond_partition_pivot_heap_1(leqElem#2(x4,x8),x8,x6,x4,x2) - Signature: {cond_partition_pivot_heap_1/5,cond_partition_pivot_heap_3/7,cond_partition_pivot_heap_4/5 ,cond_partition_pivot_heap_5/5,cond_partition_pivot_heap_7/7,cond_partition_pivot_heap_8/5 ,cond_partition_pivot_heap_9/5,leq#2/2,leqElem#2/2,main/2,partition#2/2} / {0/0,E/0,Elem/1,False/0,Pair/2 ,S/1,T/3,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {cond_partition_pivot_heap_1,cond_partition_pivot_heap_3 ,cond_partition_pivot_heap_4,cond_partition_pivot_heap_5,cond_partition_pivot_heap_7 ,cond_partition_pivot_heap_8,cond_partition_pivot_heap_9,leq#2,leqElem#2,main ,partition#2} and constructors {0,E,Elem,False,Pair,S,T,True} + Applied Processor: Ara {araHeuristics = NoHeuristics, minDegree = 1, maxDegree = 2, araTimeout = 5, araRuleShifting = Nothing} + Details: Signatures used: ---------------- 0 :: [] -(0)-> "A"(1) 0 :: [] -(0)-> "A"(0) E :: [] -(0)-> "A"(15) E :: [] -(0)-> "A"(13) Elem :: ["A"(7)] -(7)-> "A"(7) Elem :: ["A"(0)] -(0)-> "A"(0) False :: [] -(0)-> "A"(7) False :: [] -(0)-> "A"(15) Pair :: ["A"(0) x "A"(0)] -(0)-> "A"(0) Pair :: ["A"(0) x "A"(0)] -(0)-> "A"(2) Pair :: ["A"(0) x "A"(0)] -(0)-> "A"(8) Pair :: ["A"(0) x "A"(0)] -(0)-> "A"(9) Pair :: ["A"(0) x "A"(0)] -(0)-> "A"(10) Pair :: ["A"(0) x "A"(0)] -(0)-> "A"(14) S :: ["A"(1)] -(1)-> "A"(1) S :: ["A"(0)] -(0)-> "A"(0) T :: ["A"(15) x "A"(15) x "A"(15)] -(15)-> "A"(15) T :: ["A"(0) x "A"(0) x "A"(0)] -(0)-> "A"(0) True :: [] -(0)-> "A"(7) True :: [] -(0)-> "A"(15) cond_partition_pivot_heap_1 :: ["A"(7) x "A"(8) x "A"(15) x "A"(0) x "A"(15)] -(10)-> "A"(8) cond_partition_pivot_heap_3 :: ["A"(7) x "A"(8) x "A"(8) x "A"(0) x "A"(15) x "A"(0) x "A"(15)] -(15)-> "A"(8) cond_partition_pivot_heap_4 :: ["A"(0) x "A"(0) x "A"(0) x "A"(1) x "A"(0)] -(12)-> "A"(8) cond_partition_pivot_heap_5 :: ["A"(2) x "A"(0) x "A"(0) x "A"(0) x "A"(1)] -(1)-> "A"(8) cond_partition_pivot_heap_7 :: ["A"(7) x "A"(8) x "A"(0) x "A"(8) x "A"(15) x "A"(0) x "A"(15)] -(12)-> "A"(14) cond_partition_pivot_heap_8 :: ["A"(8) x "A"(0) x "A"(0) x "A"(1) x "A"(0)] -(2)-> "A"(14) cond_partition_pivot_heap_9 :: ["A"(8) x "A"(0) x "A"(0) x "A"(0) x "A"(1)] -(4)-> "A"(14) leq#2 :: ["A"(1) x "A"(0)] -(8)-> "A"(15) leqElem#2 :: ["A"(7) x "A"(0)] -(2)-> "A"(14) main :: ["A"(15) x "A"(14)] -(16)-> "A"(2) partition#2 :: ["A"(8) x "A"(15)] -(1)-> "A"(8) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "0_A" :: [] -(0)-> "A"(1) "E_A" :: [] -(0)-> "A"(1) "Elem_A" :: ["A"(1)] -(1)-> "A"(1) "False_A" :: [] -(0)-> "A"(1) "Pair_A" :: ["A"(0) x "A"(0)] -(0)-> "A"(1) "S_A" :: ["A"(1)] -(1)-> "A"(1) "T_A" :: ["A"(1) x "A"(1) x "A"(1)] -(1)-> "A"(1) "True_A" :: [] -(0)-> "A"(1) WORST_CASE(?,O(n^1))