Algorithm to compute $n^{\log k}$ in $O(\log\log k)$
The idea is to use repeated squaring. Compute $n,n^2,n^4,\ldots n^{\log k}$. To compute $n^{2^i}$ use the fact that $n^{2^i} = n^{2^{i-1}} n^{2^{i-1}}$. Note that the answer of $n^{2^{i-1}}$ will be known in the $i$th iteration.