Runtime Complexity TRS:
The TRS R consists of the following rules:

pairNs → cons(0, n__incr(n__oddNs))
oddNs → incr(pairNs)
incr(cons(X, XS)) → cons(s(X), n__incr(activate(XS)))
take(0, XS) → nil
take(s(N), cons(X, XS)) → cons(X, n__take(N, activate(XS)))
zip(nil, XS) → nil
zip(X, nil) → nil
zip(cons(X, XS), cons(Y, YS)) → cons(pair(X, Y), n__zip(activate(XS), activate(YS)))
tail(cons(X, XS)) → activate(XS)
repItems(nil) → nil
repItems(cons(X, XS)) → cons(X, n__cons(X, n__repItems(activate(XS))))
incr(X) → n__incr(X)
oddNs → n__oddNs
take(X1, X2) → n__take(X1, X2)
zip(X1, X2) → n__zip(X1, X2)
cons(X1, X2) → n__cons(X1, X2)
repItems(X) → n__repItems(X)
activate(n__incr(X)) → incr(activate(X))
activate(n__oddNs) → oddNs
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(n__zip(X1, X2)) → zip(activate(X1), activate(X2))
activate(n__cons(X1, X2)) → cons(activate(X1), X2)
activate(n__repItems(X)) → repItems(activate(X))
activate(X) → X

Rewrite Strategy: INNERMOST

Renamed function symbols to avoid clashes with predefined symbol.

Runtime Complexity TRS:
The TRS R consists of the following rules:

pairNs' → cons'(0', n__incr'(n__oddNs'))
oddNs' → incr'(pairNs')
incr'(cons'(X, XS)) → cons'(s'(X), n__incr'(activate'(XS)))
take'(0', XS) → nil'
take'(s'(N), cons'(X, XS)) → cons'(X, n__take'(N, activate'(XS)))
zip'(nil', XS) → nil'
zip'(X, nil') → nil'
zip'(cons'(X, XS), cons'(Y, YS)) → cons'(pair'(X, Y), n__zip'(activate'(XS), activate'(YS)))
tail'(cons'(X, XS)) → activate'(XS)
repItems'(nil') → nil'
repItems'(cons'(X, XS)) → cons'(X, n__cons'(X, n__repItems'(activate'(XS))))
incr'(X) → n__incr'(X)
oddNs' → n__oddNs'
take'(X1, X2) → n__take'(X1, X2)
zip'(X1, X2) → n__zip'(X1, X2)
cons'(X1, X2) → n__cons'(X1, X2)
repItems'(X) → n__repItems'(X)
activate'(n__incr'(X)) → incr'(activate'(X))
activate'(n__oddNs') → oddNs'
activate'(n__take'(X1, X2)) → take'(activate'(X1), activate'(X2))
activate'(n__zip'(X1, X2)) → zip'(activate'(X1), activate'(X2))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__repItems'(X)) → repItems'(activate'(X))
activate'(X) → X

Rewrite Strategy: INNERMOST

Sliced the following arguments:
pair'/0
pair'/1

Runtime Complexity TRS:
The TRS R consists of the following rules:

pairNs' → cons'(0', n__incr'(n__oddNs'))
oddNs' → incr'(pairNs')
incr'(cons'(X, XS)) → cons'(s'(X), n__incr'(activate'(XS)))
take'(0', XS) → nil'
take'(s'(N), cons'(X, XS)) → cons'(X, n__take'(N, activate'(XS)))
zip'(nil', XS) → nil'
zip'(X, nil') → nil'
zip'(cons'(X, XS), cons'(Y, YS)) → cons'(pair', n__zip'(activate'(XS), activate'(YS)))
tail'(cons'(X, XS)) → activate'(XS)
repItems'(nil') → nil'
repItems'(cons'(X, XS)) → cons'(X, n__cons'(X, n__repItems'(activate'(XS))))
incr'(X) → n__incr'(X)
oddNs' → n__oddNs'
take'(X1, X2) → n__take'(X1, X2)
zip'(X1, X2) → n__zip'(X1, X2)
cons'(X1, X2) → n__cons'(X1, X2)
repItems'(X) → n__repItems'(X)
activate'(n__incr'(X)) → incr'(activate'(X))
activate'(n__oddNs') → oddNs'
activate'(n__take'(X1, X2)) → take'(activate'(X1), activate'(X2))
activate'(n__zip'(X1, X2)) → zip'(activate'(X1), activate'(X2))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__repItems'(X)) → repItems'(activate'(X))
activate'(X) → X

Rewrite Strategy: INNERMOST

Infered types.

Rules:
pairNs' → cons'(0', n__incr'(n__oddNs'))
oddNs' → incr'(pairNs')
incr'(cons'(X, XS)) → cons'(s'(X), n__incr'(activate'(XS)))
take'(0', XS) → nil'
take'(s'(N), cons'(X, XS)) → cons'(X, n__take'(N, activate'(XS)))
zip'(nil', XS) → nil'
zip'(X, nil') → nil'
zip'(cons'(X, XS), cons'(Y, YS)) → cons'(pair', n__zip'(activate'(XS), activate'(YS)))
tail'(cons'(X, XS)) → activate'(XS)
repItems'(nil') → nil'
repItems'(cons'(X, XS)) → cons'(X, n__cons'(X, n__repItems'(activate'(XS))))
incr'(X) → n__incr'(X)
oddNs' → n__oddNs'
take'(X1, X2) → n__take'(X1, X2)
zip'(X1, X2) → n__zip'(X1, X2)
cons'(X1, X2) → n__cons'(X1, X2)
repItems'(X) → n__repItems'(X)
activate'(n__incr'(X)) → incr'(activate'(X))
activate'(n__oddNs') → oddNs'
activate'(n__take'(X1, X2)) → take'(activate'(X1), activate'(X2))
activate'(n__zip'(X1, X2)) → zip'(activate'(X1), activate'(X2))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__repItems'(X)) → repItems'(activate'(X))
activate'(X) → X

Types:
pairNs' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
cons' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
0' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
n__incr' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
n__oddNs' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
oddNs' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
incr' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
s' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
activate' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
take' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
nil' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
n__take' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
zip' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
pair' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
n__zip' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
tail' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
repItems' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
n__cons' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
n__repItems' :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons' → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
_hole_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'1 :: 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'
_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2 :: Nat → 0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'

Heuristically decided to analyse the following defined symbols:
oddNs', incr', activate', repItems'

They will be analysed ascendingly in the following order:
oddNs' = incr'
oddNs' = activate'
oddNs' = repItems'
incr' = activate'
incr' = repItems'
activate' = repItems'

Generator Equations:
_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(0) ⇔ 0'
_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(x, 1)) ⇔ n__incr'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(x))

The following defined symbols remain to be analysed:
incr', oddNs', activate', repItems'

They will be analysed ascendingly in the following order:
oddNs' = incr'
oddNs' = activate'
oddNs' = repItems'
incr' = activate'
incr' = repItems'
activate' = repItems'

Could not prove a rewrite lemma for the defined symbol incr'.

The following defined symbols remain to be analysed:
activate', oddNs', repItems'

They will be analysed ascendingly in the following order:
oddNs' = incr'
oddNs' = activate'
oddNs' = repItems'
incr' = activate'
incr' = repItems'
activate' = repItems'

Proved the following rewrite lemma:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, _n16))) → _*3, rt ∈ Ω(_n16)

Induction Base:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, 0)))

Induction Step:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, +(_$n17, 1)))) →_R^Ω(1)
incr'(activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, _$n17)))) →_IH
incr'(_*3)

We have rt ∈ Ω(n) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

Lemmas:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, _n16))) → _*3, rt ∈ Ω(_n16)

The following defined symbols remain to be analysed:
oddNs', incr', repItems'

They will be analysed ascendingly in the following order:
oddNs' = incr'
oddNs' = activate'
oddNs' = repItems'
incr' = activate'
incr' = repItems'
activate' = repItems'

Could not prove a rewrite lemma for the defined symbol oddNs'.

Lemmas:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, _n16))) → _*3, rt ∈ Ω(_n16)

The following defined symbols remain to be analysed:
repItems', incr'

They will be analysed ascendingly in the following order:
oddNs' = incr'
oddNs' = activate'
oddNs' = repItems'
incr' = activate'
incr' = repItems'
activate' = repItems'

Could not prove a rewrite lemma for the defined symbol repItems'.

Lemmas:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, _n16))) → _*3, rt ∈ Ω(_n16)

The following defined symbols remain to be analysed:
incr'

They will be analysed ascendingly in the following order:
oddNs' = incr'
oddNs' = activate'
oddNs' = repItems'
incr' = activate'
incr' = repItems'
activate' = repItems'

Could not prove a rewrite lemma for the defined symbol incr'.

Lemmas:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, _n16))) → _*3, rt ∈ Ω(_n16)

No more defined symbols left to analyse.

The lowerbound Ω(n) was proven with the following lemma:
activate'(_gen_0':n__oddNs':n__incr':s':nil':n__take':pair':n__zip':n__repItems':n__cons'2(+(1, _n16))) → _*3, rt ∈ Ω(_n16)