# How to tackle Big O proofs that involve multiple parameters

I am getting more and more familiar with the whole concept of time complexity but I have never encountered an example where more than one parameter is involved. Therefore, is it possible(well, I am sure it is :")) and how to prove

a^n = Θ(logn)

or any other, similar-looking expression?

c1 * logn ≤ a^n ≤ c2 * logn

where, e.g. c1 = 1 and c2 = 2,

logn ≤ a^n ≤2 * logn.

Can I go one step further and set n, to be equal e.g. 2? This way I will get

log(2) ≤ a^2 ≤ log(4)

Which is surely true(for a between ~ 0.55 and 0.77)...

...but isn't that too specific and interfere with the inequality too much? Sorry if the answer is trivial but Google is not helping and I have nobody to ask for explanation.

• If a, b, c are constants, proofs don't change a whole lot. Normal rules apply.
– Raphael
Mar 9, 2020 at 6:27
• Your inequations are all wrong ! Mar 30 at 14:27

That isn't true. As you say, it implies there are $$c_2$$ and $$N$$ so that for all $$n \ge N$$ you have $$a^n \le c_2 \log n$$. Consider:
\begin{align*} \lim_{n \to \infty} \frac{a^n}{\log n} &= \lim_{n \to \infty} \frac{a^n \log a}{1 / n} = \infty \end{align*}
Here we used l'Hôpital. But that the limit is infinite means that eventually the ratio is larger than any given $$c_2$$. In fact, it proves $$a^n = \Omega(\log n)$$.