0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In my book, there's no knowing, as asymptotic growth is stated dropping constant factors ($log_2$ is funny in this regard, as it's just a constant factor from the logarithm to any other suitable base) and leaving open things like $n_0$. $\endgroup$ – greybeard Mar 4 at 6:24
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 4 at 6:48
  • 3
    $\begingroup$ The question is meaningless. You should refuse to answer it and argue why, using the definition of $\Theta$. $\endgroup$ – Raphael Mar 4 at 6:49
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I'm sure you're having best intentions, but this is kind of "not even wrong", and doesn't answer the question the OP cited either. $\endgroup$ – Raphael Mar 4 at 6:50
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.