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.
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}
      &amp;= \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)$.