I'll do my best to explain my question but what I'm wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such:
If a $\Theta(\log_2{n})$ algorithm requires 20 seconds to execute on an input of one million elements, approximately how long should it take on an input of two million elements?
The answer it gives is 21 seconds and I'm stuck on how they come up with that number.
Basically, the complexity of an algorithm gives the relation of the change in the running time with respect to the change in the input size. You can think it as,
$log_2(1M)$ -> 20 sec
$log_2(2M)$ -> ? sec
$log_2(2M) = log_2(2 *1M) = log_2(2) + log_2(1M) = 1 + 20 = 21 sec$
If an algorithm has time complexity $T(n) \in \Theta (\log_2 n)$, then it means that $T(n)$ is bounded above and below by constant factors of $\log_2 n$ for sufficiently large $n$. This definition actually leaves a lot of room for possible $T(n)$, and the question in your textbook makes some additional assumptions (or uses a very loose definition of "approximate").
If $T(n) = \log_2 n + c$, then $T(2n) = T(n) + 1$, so $T(10^6) = 20$ implies $T(2 \cdot 10^6) = 21$.
However, it could also be that $T(n) = k \log_2 n + c$, in which case $T(2n) = T(n) + k$. Note that the complexities $\Theta(\log_2 n)$ and $\Theta(\log n)$ are equivalent, and you would typically choose the simplest possible function to express the growth rate. By writing $\Theta(\log_2 n)$, the textbook is abusing notation to let you know that $k = 1$.
Even then, more complicated expressions are possible e.g. $T(n) = \log_2 n + A \log_2 (\log_2 n) + B \cos n$. Only for sufficiently large $n$ do those additional terms become irrelevant. For any fixed $n$, the answer to your question could be arbitrarily skewed. Therefore, I would say the question is formally meaningless, and whatever intuition it helps build is outweighed by the confusion it creates.
