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.

  • $\begingroup$ If a, b, c are constants, proofs don't change a whole lot. Normal rules apply. $\endgroup$ – Raphael Mar 9 '20 at 6: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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.