I have been looking at a particular computational problem and finally reduced it down to a bound of $a^a=n$, I will try to explain what I mean by this first in one paragraph.
For example, suppose I am trying to find if an element exists in a sorted array. I can do binary search, which will require $a$ steps such that $2^a=n$. Hence we know that binary search requires $\Theta(\log n)$ steps, by solving the previous equation. Now similarly, I have a problem which upon solving I get the equation $a^a=n$ instead of $2^a=n$ which we had for binary search.
I have been informed that there is no explicit function to satisfy this. That is whatever explicit function $f(n)$ I take, $f(n)^{f(n)}$ is not equal to $n$. Not only this, I cannot write an explicit function satisfying this in the big $\Theta$ notation as well. By this what I mean is for all explicit functions $f(n)$, and for all functions $g(n)\in \Theta(n)$, we must have $f(n)^{f(n)}!=g(n)$. The second statement is a stronger statement but I have a feeling that it might be easy to prove the second statement from the first statement somehow. Also, I have no idea how to go about proving the first statement itself. Any insights regarding these would be appreciated.
