3
$\begingroup$

I read that testing the length of the input string is in DLOGTIME.

The question is how can testing the length of the input string be in DLOGTIME?

$\text{DLOGTIME} = O(\log n)$, so what number would be in $n$? (as it seems that $n$ is definitely not the length of the input string..... or is it?)

So, to summarize, can anyone show me how the algorithm performs and how it is in DLOGTIME? At this point, it seems to me that $n$ is just an arbitary number..

Note: I know what binary search is :) so you do not need to explain me about what that is.

$\endgroup$
0

2 Answers 2

6
$\begingroup$

It is hard to answer the question without further context.

Complexity is typically defined in terms of the size of the input (the number of bits needed to represent the input) and therefor depends on the representation you choose for the inputs. (More formally, a language or a formal computational problem is defined over strings of the alphabet, and the complexity is defined based on that, how you interpret these strings as objects (e.g. graphs, natural numbers, etc.) doesn't have an effect on the complexity, a "problem" corresponds to several (formal) computational problems based on the representations used.)

The complexity class $\mathsf{DLogTime}$ is defined as deterministic logarithmic time in the input size, $n$ is the size of the input. I guess you are confused because we typically use Turing machines for defining complexity classes but that may not make sense for sublinear time since one cannot even read the input. For sublinear time the model of computation is typically considered to be Random Access Machines where one can access any bit of the input directly without going over all previous bits using indexes (kind of similar to how memory works in real computers).

One can find the length of the input in two steps using an index variable (a binary number):

  1. Start from 1 and repeatedly double the value till the memory square corresponding to it is blank (an upper bound on the length of the input),

  2. Do a binary search to find the last nonblank symbol. (Blank symbol is not used in the input.)

If the input is a string of length $n$ then this algorithm will find the size of the input in binary in time $O(\lg n)$.

$\endgroup$
1
$\begingroup$

The model for $\text{DLOGTIME}$ is such that the input is given on a tape which has random access so you can "read" parts of it without "counting" the time needed to move the end. If so, then binary search solves it quite straightforwardly, and maybe this is what you meant to ask.

Changing the model is necessary when discussing complexity classes which are sub-linear, so that the machine will be able to read the input without "consuming" resources. As a similar example, the class $\text{DL}$ (deterministic logarithmic space) defines the model as follows: the input is given on a read-only input tape; in addition there is a read/write working tape. The space you use is counted only for the working tape, which means you are able to read the entire input without consuming any memory.

$\endgroup$

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.