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

1 Answer 1

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$
1
  • $\begingroup$ but sir, the log n function disobeys the law of f(n) >=n of time constructble functions ,doesn't it? $\endgroup$
    – kapil
    Commented Jul 5, 2020 at 10:06

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.