WORST_CASE(?,O(n^1)) * Step 1: Bounds WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: decrease(Cons(x,xs)) -> decrease(xs) decrease(Nil()) -> number42(Nil()) goal(x) -> decrease(x) number42(x) -> Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Nil())))))))))))))))))))))))))))))))))))))))))) - Signature: {decrease/1,goal/1,number42/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {decrease,goal,number42} and constructors {Cons,Nil} + Applied Processor: Bounds {initialAutomaton = minimal, enrichment = match} + Details: The problem is match-bounded by 2. The enriched problem is compatible with follwoing automaton. Cons_0(2,2) -> 2 Cons_1(3,3) -> 44 Cons_1(3,4) -> 1 Cons_1(3,5) -> 4 Cons_1(3,6) -> 5 Cons_1(3,7) -> 6 Cons_1(3,8) -> 7 Cons_1(3,9) -> 8 Cons_1(3,10) -> 9 Cons_1(3,11) -> 10 Cons_1(3,12) -> 11 Cons_1(3,13) -> 12 Cons_1(3,14) -> 13 Cons_1(3,15) -> 14 Cons_1(3,16) -> 15 Cons_1(3,17) -> 16 Cons_1(3,18) -> 17 Cons_1(3,19) -> 18 Cons_1(3,20) -> 19 Cons_1(3,21) -> 20 Cons_1(3,22) -> 21 Cons_1(3,23) -> 22 Cons_1(3,24) -> 23 Cons_1(3,25) -> 24 Cons_1(3,26) -> 25 Cons_1(3,27) -> 26 Cons_1(3,28) -> 27 Cons_1(3,29) -> 28 Cons_1(3,30) -> 29 Cons_1(3,31) -> 30 Cons_1(3,32) -> 31 Cons_1(3,33) -> 32 Cons_1(3,34) -> 33 Cons_1(3,35) -> 34 Cons_1(3,36) -> 35 Cons_1(3,37) -> 36 Cons_1(3,38) -> 37 Cons_1(3,39) -> 38 Cons_1(3,40) -> 39 Cons_1(3,41) -> 40 Cons_1(3,42) -> 41 Cons_1(3,43) -> 42 Cons_1(3,44) -> 43 Cons_2(45,46) -> 1 Cons_2(47,48) -> 46 Cons_2(49,50) -> 48 Cons_2(51,52) -> 50 Cons_2(53,54) -> 52 Cons_2(55,56) -> 54 Cons_2(57,58) -> 56 Cons_2(59,60) -> 58 Cons_2(61,62) -> 60 Cons_2(63,64) -> 62 Cons_2(65,66) -> 64 Cons_2(67,68) -> 66 Cons_2(69,70) -> 68 Cons_2(71,72) -> 70 Cons_2(73,74) -> 72 Cons_2(75,76) -> 74 Cons_2(77,78) -> 76 Cons_2(79,80) -> 78 Cons_2(81,82) -> 80 Cons_2(83,84) -> 82 Cons_2(85,86) -> 84 Cons_2(87,88) -> 86 Cons_2(89,90) -> 88 Cons_2(91,92) -> 90 Cons_2(93,94) -> 92 Cons_2(95,96) -> 94 Cons_2(97,98) -> 96 Cons_2(99,100) -> 98 Cons_2(101,102) -> 100 Cons_2(103,104) -> 102 Cons_2(105,106) -> 104 Cons_2(107,108) -> 106 Cons_2(109,110) -> 108 Cons_2(111,112) -> 110 Cons_2(113,114) -> 112 Cons_2(115,116) -> 114 Cons_2(117,118) -> 116 Cons_2(119,120) -> 118 Cons_2(121,122) -> 120 Cons_2(123,124) -> 122 Cons_2(125,126) -> 124 Cons_2(127,128) -> 126 Nil_0() -> 2 Nil_1() -> 3 Nil_2() -> 45 Nil_2() -> 47 Nil_2() -> 49 Nil_2() -> 51 Nil_2() -> 53 Nil_2() -> 55 Nil_2() -> 57 Nil_2() -> 59 Nil_2() -> 61 Nil_2() -> 63 Nil_2() -> 65 Nil_2() -> 67 Nil_2() -> 69 Nil_2() -> 71 Nil_2() -> 73 Nil_2() -> 75 Nil_2() -> 77 Nil_2() -> 79 Nil_2() -> 81 Nil_2() -> 83 Nil_2() -> 85 Nil_2() -> 87 Nil_2() -> 89 Nil_2() -> 91 Nil_2() -> 93 Nil_2() -> 95 Nil_2() -> 97 Nil_2() -> 99 Nil_2() -> 101 Nil_2() -> 103 Nil_2() -> 105 Nil_2() -> 107 Nil_2() -> 109 Nil_2() -> 111 Nil_2() -> 113 Nil_2() -> 115 Nil_2() -> 117 Nil_2() -> 119 Nil_2() -> 121 Nil_2() -> 123 Nil_2() -> 125 Nil_2() -> 127 Nil_2() -> 128 decrease_0(2) -> 1 decrease_1(2) -> 1 goal_0(2) -> 1 number42_0(2) -> 1 number42_1(3) -> 1 * Step 2: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: decrease(Cons(x,xs)) -> decrease(xs) decrease(Nil()) -> number42(Nil()) goal(x) -> decrease(x) number42(x) -> Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Nil())))))))))))))))))))))))))))))))))))))))))) - Signature: {decrease/1,goal/1,number42/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {decrease,goal,number42} and constructors {Cons,Nil} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))