WORST_CASE(?,O(1)) * Step 1: NaturalPI WORST_CASE(?,O(1)) + Considered Problem: - Strict TRS: f(g(h(a(),b()),c()),d()) -> if(e(),f(.(b(),g(h(a(),b()),c())),d()),f(c(),d'())) f(g(i(a(),b(),b'()),c()),d()) -> if(e(),f(.(b(),c()),d'()),f(.(b'(),c()),d'())) - Signature: {f/2} / {./2,a/0,b/0,b'/0,c/0,d/0,d'/0,e/0,g/2,h/2,i/3,if/3} - Obligation: innermost runtime complexity wrt. defined symbols {f} and constructors {.,a,b,b',c,d,d',e,g,h,i,if} + Applied Processor: NaturalPI {shape = StronglyLinear, restrict = NoRestrict, uargs = UArgs, urules = URules, selector = Nothing} + Details: We apply a polynomial interpretation of kind constructor-based(stronglyLinear): The following argument positions are considered usable: none Following symbols are considered usable: {f} TcT has computed the following interpretation: p(.) = x1 + x2 p(a) = 0 p(b) = 0 p(b') = 0 p(c) = 0 p(d) = 0 p(d') = 0 p(e) = 0 p(f) = 8 p(g) = 2 p(h) = 0 p(i) = 0 p(if) = 4 Following rules are strictly oriented: f(g(h(a(),b()),c()),d()) = 8 > 4 = if(e(),f(.(b(),g(h(a(),b()),c())),d()),f(c(),d'())) f(g(i(a(),b(),b'()),c()),d()) = 8 > 4 = if(e(),f(.(b(),c()),d'()),f(.(b'(),c()),d'())) Following rules are (at-least) weakly oriented: WORST_CASE(?,O(1))