* Step 1: Sum WORST_CASE(Omega(n^1),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:
Sum {left = someStrategy, right = someStrategy}
+ Details:
()
** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(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:
DecreasingLoops {bound = AnyLoop, narrow = 10}
+ Details:
The system has following decreasing Loops:
decrease(y){y -> Cons(x,y)} =
decrease(Cons(x,y)) ->^+ decrease(y)
= C[decrease(y) = decrease(y){}]
** Step 1.b: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 1.b: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(Omega(n^1),O(n^1))