# Tag Info

3

No, since the Ackermann function grows faster than any primitive recursive function. The iterated logarithm is one of the two inverse functions of tetration. As a primitive recursive function, Tetration with base 2 is "roughly" equivalent to $A(4,n)$, where $A(m,n)$ is the Ackermann function of two variables . $A(n,n)$ is assumed to be the ...

2

We prove by induction that $T(n) \leq Cn^n$, where $C = \max(T(2),4/3)$. The base cases are clear. For the inductive case, $$T(n) = 2^nT(n/2) + n^n \leq C2^n (n/2)^{n/2} + n^n = C\left(\frac{2}{n}\right)^{n/2} n^n + n^n \leq (C/4 + 1)n^n \leq Cn^n.$$ On the other hand, clearly $T(n) \geq n^n$. Hence $T(n) = \Theta(n^n)$. In fact, if we work a bit harder, ...

1

For your question in the title,$\ log(n)\in O(n)$ is true. For what you seem to actually be looking for. The the "is element of" relation, denoted by $\in$, is not specific to algorithms and complexity theory, but is a concept from set theory that is used everywhere throughout pure and applied mathematics. Where$\ O(n)$ is a "set" of ...

Only top voted, non community-wiki answers of a minimum length are eligible