Q) For parameters $'a'$ and $'b'$ both of which are $\omega(1)$, Now, consider the recurrence $T(n) = T(n^{\frac{1}{a}}) + 1$ with base condition $T(b) = 1$ then $T(n)$ is ?
Here, I am not getting the meaning of the statement "For parameters $'a'$ and $'b'$ both of which are $\omega(1)$". Can anyone please explain it.
Using Back-Substitution, the solution of given recurrence is : $\Theta(log_alog_bn)$. By changing bases, it can be $\Theta(log_2log_2 n)$ or $\Theta(log_blog_a n)$ if $a$ and $b$ are constants. On considering $a$ and $b$ as non-constant functions of $'n'$ then only solution is: $\Theta(log_alog_b n)$ but then what is the meaning of base condition $T(b)=1$ i.e. $T(f(n))=1.$ Here, left side $T(f(n))$ is like function of function and right side $1$ is constant then how both can be equal. Also, if both $a$ and $b$ are $n$ then solution will be $\Theta(0)$ which does not have any meaning.
Definition of small-omega says:
$f(n) \in \omega(g(n)) :$
$\omega(g(n))= \{ f(n) : $ for any positive constant $c>0$ there exists a constant $n_0$ such that $0 \leq cg(n) < f(n)$ for all $n \geq 0\}.$
So, whether $'a'$ and $'b'$ should be taken as constant or some function of $n$ except function $'n'$ and what should be the meaning of base condition in that case ?
Please help.