I have found some interesting exercises on the Internet about O-notation. Many of the examples I found were feasible, but with these two I am not quite sure how to find the solution, so I ask here. The following is to be determined there:
Indicate whether $f=O(g)$, or $f=Ω(g)$ or both, in which case $f=Θ(g)$ applies
In the following I am interested in these two tasks, the solution of which I cannot quite comprehend:
1.) $f(n)=n^{0.1}, \quad g(n) = (log(n))^{10}$, Solution is $f=Ω(g)$ but why this is the case?
2.) $f(n) = 2^{k\cdot \log(n)}, \quad g(n) = n^k$, No solution is named here, but I'am interested in a solution
It would be very kind if someone could help me. I have already solved other tasks for O Notation for personal practice, but the two tasks were not solvable for me...
I assume $k>0$.
$$2^{k\log n}=e^{k\log n\log 2}=n^{k\log 2}\le n^k$$ hence $f=O(g)$.
On the other hand, $f=\Omega(g)$ is not possible because
$$cn^{k\log 2}\ge n^k$$ would require $$c\ge n^{k(1-\log2)}.$$