3
$\begingroup$

Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$.

The time complexity of $f$ is $O(n_{_{old}})$ = $O(\log\ n_{_{new}})$, is it admited to say that $f$ is a $O(\log n)$ function ?

$\endgroup$

2 Answers 2

5
$\begingroup$

The running time of a function is usually measured with respect to the length of the input, which is represented by the parameter $n$. In your case, if the input is the integer $m$ then the input length is $n = \log m$ and the running time is $O(m) = O(2^n)$.

For functions whose output is much larger than the input, it makes sense to measure the complexity with respect to the size of the output. In your case, the function runs in linear time with respect to the size of the output.

In other cases it might be meaningful to use other parameters to measure the running time of a function. For example, functions on graphs are sometimes measured with respect to the number of vertices and the number of edges. The end goal is usually to analyze the running time of some function in terms of its input length, but on the way it is OK to measure the running time of subroutines in terms of other parameters.

$\endgroup$
2
$\begingroup$

No. The input for $f$ is $n_{\text{old}}$, which, as you mentioned, is stored using $O(\log n_{\text{old}})$ space. Thus the upper bound $O(n_{\text{old}})$ on the time complexity of $f$ is actually exponential in the input size, so all you can say is that $f$ is computable in $O(2^n)$.

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