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

zeros → cons(0, n__zeros)
U11(tt, L) → s(length(activate(L)))
U21(tt) → nil
U31(tt, IL, M, N) → cons(activate(N), n__take(activate(M), activate(IL)))
and(tt, X) → activate(X)
isNat(n__0) → tt
isNat(n__length(V1)) → isNatList(activate(V1))
isNat(n__s(V1)) → isNat(activate(V1))
isNatIList(V) → isNatList(activate(V))
isNatIList(n__zeros) → tt
isNatIList(n__cons(V1, V2)) → and(isNat(activate(V1)), n__isNatIList(activate(V2)))
isNatList(n__nil) → tt
isNatList(n__cons(V1, V2)) → and(isNat(activate(V1)), n__isNatList(activate(V2)))
isNatList(n__take(V1, V2)) → and(isNat(activate(V1)), n__isNatIList(activate(V2)))
length(nil) → 0
length(cons(N, L)) → U11(and(isNatList(activate(L)), n__isNat(N)), activate(L))
take(0, IL) → U21(isNatIList(IL))
take(s(M), cons(N, IL)) → U31(and(isNatIList(activate(IL)), n__and(n__isNat(M), n__isNat(N))), activate(IL), M, N)
zeros → n__zeros
take(X1, X2) → n__take(X1, X2)
0 → n__0
length(X) → n__length(X)
s(X) → n__s(X)
cons(X1, X2) → n__cons(X1, X2)
isNatIList(X) → n__isNatIList(X)
nil → n__nil
isNatList(X) → n__isNatList(X)
isNat(X) → n__isNat(X)
and(X1, X2) → n__and(X1, X2)
activate(n__zeros) → zeros
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(n__0) → 0
activate(n__length(X)) → length(activate(X))
activate(n__s(X)) → s(activate(X))
activate(n__cons(X1, X2)) → cons(activate(X1), X2)
activate(n__isNatIList(X)) → isNatIList(X)
activate(n__nil) → nil
activate(n__isNatList(X)) → isNatList(X)
activate(n__isNat(X)) → isNat(X)
activate(n__and(X1, X2)) → and(activate(X1), X2)
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:

zeros' → cons'(0', n__zeros')
U11'(tt', L) → s'(length'(activate'(L)))
U21'(tt') → nil'
U31'(tt', IL, M, N) → cons'(activate'(N), n__take'(activate'(M), activate'(IL)))
and'(tt', X) → activate'(X)
isNat'(n__0') → tt'
isNat'(n__length'(V1)) → isNatList'(activate'(V1))
isNat'(n__s'(V1)) → isNat'(activate'(V1))
isNatIList'(V) → isNatList'(activate'(V))
isNatIList'(n__zeros') → tt'
isNatIList'(n__cons'(V1, V2)) → and'(isNat'(activate'(V1)), n__isNatIList'(activate'(V2)))
isNatList'(n__nil') → tt'
isNatList'(n__cons'(V1, V2)) → and'(isNat'(activate'(V1)), n__isNatList'(activate'(V2)))
isNatList'(n__take'(V1, V2)) → and'(isNat'(activate'(V1)), n__isNatIList'(activate'(V2)))
length'(nil') → 0'
length'(cons'(N, L)) → U11'(and'(isNatList'(activate'(L)), n__isNat'(N)), activate'(L))
take'(0', IL) → U21'(isNatIList'(IL))
take'(s'(M), cons'(N, IL)) → U31'(and'(isNatIList'(activate'(IL)), n__and'(n__isNat'(M), n__isNat'(N))), activate'(IL), M, N)
zeros' → n__zeros'
take'(X1, X2) → n__take'(X1, X2)
0' → n__0'
length'(X) → n__length'(X)
s'(X) → n__s'(X)
cons'(X1, X2) → n__cons'(X1, X2)
isNatIList'(X) → n__isNatIList'(X)
nil' → n__nil'
isNatList'(X) → n__isNatList'(X)
isNat'(X) → n__isNat'(X)
and'(X1, X2) → n__and'(X1, X2)
activate'(n__zeros') → zeros'
activate'(n__take'(X1, X2)) → take'(activate'(X1), activate'(X2))
activate'(n__0') → 0'
activate'(n__length'(X)) → length'(activate'(X))
activate'(n__s'(X)) → s'(activate'(X))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__isNatIList'(X)) → isNatIList'(X)
activate'(n__nil') → nil'
activate'(n__isNatList'(X)) → isNatList'(X)
activate'(n__isNat'(X)) → isNat'(X)
activate'(n__and'(X1, X2)) → and'(activate'(X1), X2)
activate'(X) → X

Rewrite Strategy: INNERMOST

Infered types.

Rules:
zeros' → cons'(0', n__zeros')
U11'(tt', L) → s'(length'(activate'(L)))
U21'(tt') → nil'
U31'(tt', IL, M, N) → cons'(activate'(N), n__take'(activate'(M), activate'(IL)))
and'(tt', X) → activate'(X)
isNat'(n__0') → tt'
isNat'(n__length'(V1)) → isNatList'(activate'(V1))
isNat'(n__s'(V1)) → isNat'(activate'(V1))
isNatIList'(V) → isNatList'(activate'(V))
isNatIList'(n__zeros') → tt'
isNatIList'(n__cons'(V1, V2)) → and'(isNat'(activate'(V1)), n__isNatIList'(activate'(V2)))
isNatList'(n__nil') → tt'
isNatList'(n__cons'(V1, V2)) → and'(isNat'(activate'(V1)), n__isNatList'(activate'(V2)))
isNatList'(n__take'(V1, V2)) → and'(isNat'(activate'(V1)), n__isNatIList'(activate'(V2)))
length'(nil') → 0'
length'(cons'(N, L)) → U11'(and'(isNatList'(activate'(L)), n__isNat'(N)), activate'(L))
take'(0', IL) → U21'(isNatIList'(IL))
take'(s'(M), cons'(N, IL)) → U31'(and'(isNatIList'(activate'(IL)), n__and'(n__isNat'(M), n__isNat'(N))), activate'(IL), M, N)
zeros' → n__zeros'
take'(X1, X2) → n__take'(X1, X2)
0' → n__0'
length'(X) → n__length'(X)
s'(X) → n__s'(X)
cons'(X1, X2) → n__cons'(X1, X2)
isNatIList'(X) → n__isNatIList'(X)
nil' → n__nil'
isNatList'(X) → n__isNatList'(X)
isNat'(X) → n__isNat'(X)
and'(X1, X2) → n__and'(X1, X2)
activate'(n__zeros') → zeros'
activate'(n__take'(X1, X2)) → take'(activate'(X1), activate'(X2))
activate'(n__0') → 0'
activate'(n__length'(X)) → length'(activate'(X))
activate'(n__s'(X)) → s'(activate'(X))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__isNatIList'(X)) → isNatIList'(X)
activate'(n__nil') → nil'
activate'(n__isNatList'(X)) → isNatList'(X)
activate'(n__isNat'(X)) → isNat'(X)
activate'(n__and'(X1, X2)) → and'(activate'(X1), X2)
activate'(X) → X

Types:
zeros' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
cons' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
0' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__zeros' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
U11' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
tt' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
s' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
length' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
activate' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
U21' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
nil' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
U31' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__take' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
and' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
isNat' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__0' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__length' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
isNatList' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__s' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
isNatIList' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__cons' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__isNatIList' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__nil' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__isNatList' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__isNat' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
take' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
n__and' :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and' → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
_hole_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'1 :: n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'
_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2 :: Nat → n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'

Heuristically decided to analyse the following defined symbols:
length', activate', and', isNat', isNatList', isNatIList'

They will be analysed ascendingly in the following order:
length' = activate'
length' = and'
length' = isNat'
length' = isNatList'
length' = isNatIList'
activate' = and'
activate' = isNat'
activate' = isNatList'
activate' = isNatIList'
and' = isNat'
and' = isNatList'
and' = isNatIList'
isNat' = isNatList'
isNat' = isNatIList'
isNatList' = isNatIList'

Generator Equations:
_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(0) ⇔ n__zeros'
_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(+(x, 1)) ⇔ n__take'(n__zeros', _gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(x))

The following defined symbols remain to be analysed:
and', length', activate', isNat', isNatList', isNatIList'

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

The following defined symbols remain to be analysed:
activate', length', isNat', isNatList', isNatIList'

Proved the following rewrite lemma:
activate'(_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(_n18)) → _*3, rt ∈ Ω(_n18)

Induction Base:
activate'(_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(0))

Induction Step:
activate'(_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(+(_$n19, 1))) →_R^Ω(1)
take'(activate'(n__zeros'), activate'(_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(_$n19))) →_R^Ω(1)
take'(n__zeros', activate'(_gen_n__zeros':tt':n__take':n__0':n__length':n__s':n__cons':n__isNatIList':n__nil':n__isNatList':n__isNat':n__and'2(_$n19))) →_IH
take'(n__zeros', _*3)

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