patternModerate
Why is log(n) a space-constructible function?
Viewed 0 times
whyspacelogfunctionconstructible
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#84154, answer score: 12
Revisions (0)
No revisions yet.