1
$\begingroup$

Say we had a function $4^k$.

The asymptotic of this function would be $\Theta(4^k)$, and thus we would say the function has exponential run-time.

But what if $k = \log{n}$? Then our same function would be $4^k = 4^{\log{n}} = n^{\log{4}} \in \Theta(n^{\log{4}})$.

(Step 2 to 3 is accomplished via a change of logarithm base).

Would we now say the function runs in polynomial time?

Or something more nuanced, like

“The function is exponential in respect to k, and polynomial in respect to n”?

$\endgroup$
3
$\begingroup$

Your question is more a question about language than about computer science and you are confusing functions and runtimes of algorithms.

$O, \Theta, o$ are mathematical tools to compare functions but it stops there. Functions are functions, mapping values to values and do not have a "runtime".

Algorithms have runtime which is the function that maps a size $n$ with the maximal time needed by this algorithm to solve instances of size $n$.

$O, \Theta...$ notations are about functions. In your first example, you have a function $k \mapsto 4^k$. This function is a function of $k$ and grows exponentially. This function of $k$ is indeed $\Theta(4^k)$ but it is also $\Theta(4^{k+1})$ because $(1/4) 4^{k+1} \leq 4^k \leq 4^{k+1} $. It is also $\Theta(4^{k+489})$ for what it is worth. So there is nothing unique about this. It is simply a way of focusing on the main part of a function when we are only interested in its asymptomatic behavior.

If you have an algorithm which runs in time $4^k$ it means its runtime, which is a function, is $4^k$, that is, when the size of the input is $k$ then the algorithm finished in less that $4^k$ steps and for some input of size $k$, you need $4^k$ steps. In this case, this algorithm runs in exponential time.

If you have an algorithm which runs in time $\Theta(4^k)$, it means that the runtime of the algorithm, which is a function, is $\Theta(4^k)$ and indeed you have an exponential time algorithm.

If you have an algorithm which runs in time $O(4^k)$, it means that the runtime of the algorithm, which is a function, is $O(4^k)$. In this case, you cannot say for sure that your algorithm runs in exponential time. It may well be that the true runtime of your algorithm is $\Theta(k)$ but that you haven't proven it yet.

Now you ask what if "$k=\log(n)$". In this case, you are now talking about the following fuction: $n \mapsto 4^{\log n}$ which turns out to be $n^{\log 4}$ which is indeed bounded by a polynomial in $n$. So if you have an algorithm which runs in time $n^{\log 4}$ on input of size $n$ then this algorithm runs in polynomial time.

But if your algorithm runs in time $n^{\log 4}$ for input of size $\log(n)$, then this algorithm runs in exponential time.

$\endgroup$
3
$\begingroup$

The asymptotic behaviour of a function always depends on the parameter in the function. So for your example, I'd say that claiming that the function is exponential w.r.t. $k$, but polynomial w.r.t. to $n$ is correct.

When we look at the running time of algorithms, we consider it to be a function of the size of the input (usually the number of bits in a binary encoding). So, for an algorithm, it is always well defined whether it is for instance polynomial or not, but this can depend on how you define or encode your input.

$\endgroup$
  • $\begingroup$ Thanks! If an algorithm is polynomial in terms of bits, it is also polynomial in terms of digits since change of base is a constant factor. If there existed a numbering system in which change of base was a non constant factor, does this mean the runtime of the algorithm can be reduced as well? Say, N is n-bits (so it’s < 2^n in size), but in a new numering system it was log-n “bits”. $\endgroup$ – Sentient Jan 19 '18 at 8:41
  • $\begingroup$ @Sentient There is no need to bring up new bases. There is one base where the change is not a constant factor: unary. Indeed, for all bases but unary, we can encode a number n in $\Theta(\log n)$ bits, but for unary we must use $\Theta(n)$ bits. Algorithms where them being polynomial depends on whether the input is encoded in binary or unary are called Pseudo-Polynomial. $\endgroup$ – Discrete lizard Jan 19 '18 at 12:13

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.