Today I read the following text in CLRS:

We say that an algorithm solves a concrete problem in time $O(T(n))$ if, when it is provided a problem instance $i$ of length $n = |i|$, the algorithm can produce the solution in $O(T(n))$ time

It is ambiguous for me, because if we consider a problem in which a number $n$ is given and we have to print $1$ for $n$ times, and our input is the number $n$ in binary format, our input has a size of $O(lg(n))$, and since we do an action $n$ times, the algorithm runs in $O(n)$, and since $O(n) = O(2^{lg(n)})$, the algorithm is exponential.

What am I doing wrong here?


1 Answer 1


You are not doing anything wrong. Typically, you would want to consider the running time with respect to some variable defined in the question. In this case, you could either consider it to be linear in $n$, or to be exponential in the number of bits in the input.

When talking about formal algorithms in the context of turing machines, the running time is defined with respect to the size of the input (which in this case would result in an exponential algorithm).

In other contexts, the running time is usually calculated with respect to one of the following things:

  1. Number of elements in the input list, if the problem's input is a list
  2. The values given in the input (for example, $n$ in this case)
  3. The size of the input in bits
  • $\begingroup$ So this problem is not considered a polynomial-solvable problem? $\endgroup$ May 22, 2021 at 19:58
  • 1
    $\begingroup$ Specifically what you described, yep. Its not polynomial-solvable using their definition $\endgroup$
    – nir shahar
    May 22, 2021 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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