We write $f(n) = Õ(g(n))$ if $f(n) = O(g(n)\log^k(g(n))$ for some natural $k$. (we call $Õ$ "soft-O")
My question is: If $f(n) = Õ(g(n)\log^a(g(n)))$ for some natural $a$, is then $f(n) = Õ(g(n))$ as well?
The question could be rephrased like this: if $h(n) = Õ(g(n))$ and $f(n) = Õ(h(n))$, is then $f(n) = Õ(g(n))$? (which would imply that soft-O notation is in some sense transitive)
I am actually particularly interested in the case when $g(n) = \log^7(n)$ and $a = 1$, but this particular problem also made me interested in the general problem.
I've tried figuring the problem out on my own but I didn't have any idea how to prove this or find a counterexample.
Yes it is transitive, assuming all functions tend to $\infty$ and you are only interested in the asymptotics as $n\to\infty$. So the functions involved satisfy $$1\ll\log^m f(n)\ll f(n),\quad\text{for any }m\ge0.\tag{$\star$}$$
Now suppose $h(n)=\tilde O(g(n))$ and $f(n)=\tilde O(h(n))$. This means that $f(n)\le Ah(n)\log^k h(n)$ and $h(n)\le Bg(n)\log^\ell g(n)$ for all $n$ large enough and some constants $A,B,k,\ell>0$. Then (using monotonicity of $\log$): \begin{align*}f(n)&\le A\cdot\left(Bg(n)\log^\ell g(n)\right)\cdot\log ^k\left(Bg(n)\log^\ell g(n)\right)\\&\le C\,g(n)\cdot\left(\log^kg(n)\right)\cdot\left(\log^\ell g(n)\right)\\& =Cg(n)\log^{k+\ell}g(n),\end{align*} for some constant $C>0$, because (by $(\star)$) $$\log^k\left(Bg(n)\log^\ell g(n)\right)\le3^k\left\{\log^kB+\log^k g(n)+\log^k\left(\log^\ell g(n)\right)\right\}=O\left(\log^kg(n)\right).$$