In my problem I am trying to find the $\mathcal O(\cdot)$ complexity expression for how value $k$ grows as a function of parameter $p$. I've come up with the following expression from considering my problem:
$$ k+1 \ge \log_{p+1}[p(p!)2^p-1]. $$
What is the proper way to reduce this expression "to it's essence" and write down what the $\mathcal O(\cdot)$ complexity of $k$ as a funtion of $p$ is?
As a first step, we can try to simplify the expression by eliminating terms that look insignificant to get the idea of what happens, and justify what we did later.
So we can begin by getting rid of the $+1$ and $-1$ terms to make things look simpler, getting a lower bound on $k$ of the form $$ \log_p \left(p \cdot p! \cdot 2^p\right) = \frac{\log p + \log p! + \log 2^p}{\log p}. $$ Here, the highest-order term is $\frac{\log p!}{\log p}$; you might already know that $\log p! = \Theta(p \log p)$, so this term is $\Theta(p)$. Lagging behind this is $\frac{\log 2^p}{\log p} = \Theta(\frac{p}{\log p})$, and finally there's the completely insignificant $\frac{\log p}{\log p} = 1$.
Now we can go back and fill in some gaps in our justification, knowing what kinds of terms end up mattering and don't. For example, we might add a first step of bounding $$ \frac{\log p!}{2 \log p} \le \frac{\log p!}{\log (p+1)} \le \frac{\log (p \cdot p! \cdot 2^p-1)}{\log (p+1)} \le \frac{\log (p! \cdot 4^p)}{\log p}.$$ These comparisons should be true for all $p\ge 2$ or so, and the same argument shows that all of these are of order $\Theta(p)$.
So we get a final answer of $k = \Omega(p)$, assuming we can remember what all of those variations on big-Oh notation actually mean.