7
$\begingroup$

According to "Constructible function", Wikipedia:

In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n).

But $\log\left(n\right)$ doesn't map onto natural numbers but to real numbers.

Why is $\log\left(n\right)$ nevertheless a space-constructible function?

$\endgroup$
12
$\begingroup$

Because when we write $\log n$ it's either in a context where it doesn't matter (e.g. Landau bounds) or with the implicit meaning of $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.

It certainly doesn't make sense to talk about constructible functions with real range, I would assume your source is talking about $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.

$\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.