I'm trying to simplify $\Theta(lg^k(n/2))$.
I believe it's $\Theta(lg^kn)$ but i don't know if the following proof is correct... i'd love to receive some input
I tried doing -
$$\Theta(lg^k(n/2))=\Theta(lg(n/2)*lg(n/2)*lg(n/2)*...*lg(n/2))=\Theta((lg\,n-lg\,2)*(lg\,n-lg\,2)*(lg\,n-lg\,2)*...*(lg\,n-lg\,2))=\Theta(\Theta(lg\,n)^k)=\Theta(lg^kn)$$
The upper O-bound is trivial.
To establish the lower bound,
consider the following limit and apply L Hospital rule repeatedly $$\lim_{x\to\infty}\frac{\lg^{k}2x}{\lg^{k}x}$$
Note that $$\dfrac{d}{dx}\left(\lg2x\right) =\dfrac{d}{dx}\left(\lg x\right)$$