WORST_CASE(?,O(n^1)) * Step 1: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: findMin#1(E()) -> ErrorElem() findMin#1(T(E(),x6,x17)) -> x6 findMin#1(T(T(x10,x12,x14),x6,x17)) -> findMin#1(T(x10,x12,x14)) main(x0) -> findMin#1(x0) - Signature: {findMin#1/1,main/1} / {E/0,ErrorElem/0,T/3} - Obligation: innermost runtime complexity wrt. defined symbols {findMin#1,main} and constructors {E,ErrorElem,T} + Applied Processor: NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(linear): The following argument positions are considered usable: none Following symbols are considered usable: {findMin#1,main} TcT has computed the following interpretation: p(E) = 0 p(ErrorElem) = 2 p(T) = x1 + x2 p(findMin#1) = 9 + 8*x1 p(main) = 9 + 9*x1 Following rules are strictly oriented: findMin#1(E()) = 9 > 2 = ErrorElem() findMin#1(T(E(),x6,x17)) = 9 + 8*x6 > x6 = x6 Following rules are (at-least) weakly oriented: findMin#1(T(T(x10,x12,x14),x6,x17)) = 9 + 8*x10 + 8*x12 + 8*x6 >= 9 + 8*x10 + 8*x12 = findMin#1(T(x10,x12,x14)) main(x0) = 9 + 9*x0 >= 9 + 8*x0 = findMin#1(x0) * Step 2: NaturalPI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: findMin#1(T(T(x10,x12,x14),x6,x17)) -> findMin#1(T(x10,x12,x14)) main(x0) -> findMin#1(x0) - Weak TRS: findMin#1(E()) -> ErrorElem() findMin#1(T(E(),x6,x17)) -> x6 - Signature: {findMin#1/1,main/1} / {E/0,ErrorElem/0,T/3} - Obligation: innermost runtime complexity wrt. defined symbols {findMin#1,main} and constructors {E,ErrorElem,T} + Applied Processor: NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(linear): The following argument positions are considered usable: none Following symbols are considered usable: {findMin#1,main} TcT has computed the following interpretation: p(E) = 0 p(ErrorElem) = 3 p(T) = 1 + x1 + x2 p(findMin#1) = 9 + 8*x1 p(main) = 10 + 8*x1 Following rules are strictly oriented: findMin#1(T(T(x10,x12,x14),x6,x17)) = 25 + 8*x10 + 8*x12 + 8*x6 > 17 + 8*x10 + 8*x12 = findMin#1(T(x10,x12,x14)) main(x0) = 10 + 8*x0 > 9 + 8*x0 = findMin#1(x0) Following rules are (at-least) weakly oriented: findMin#1(E()) = 9 >= 3 = ErrorElem() findMin#1(T(E(),x6,x17)) = 17 + 8*x6 >= x6 = x6 * Step 3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: findMin#1(E()) -> ErrorElem() findMin#1(T(E(),x6,x17)) -> x6 findMin#1(T(T(x10,x12,x14),x6,x17)) -> findMin#1(T(x10,x12,x14)) main(x0) -> findMin#1(x0) - Signature: {findMin#1/1,main/1} / {E/0,ErrorElem/0,T/3} - Obligation: innermost runtime complexity wrt. defined symbols {findMin#1,main} and constructors {E,ErrorElem,T} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))